Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Comb

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHaving endured all the hardships, Lara Croft finally found herself in a room with treasures. To her surprise she didn't find golden mountains there. Lara looked around and noticed on the floor a painted table *n* × *m* panels in size with integers written on the panels. There also was a huge number of stones lying by the wall. On the pillar near the table Lara found a guidance note which said that to get hold of the treasures one has to choose some non-zero number of the first panels in each row of the table and put stones on all those panels to push them down. After that she will receive a number of golden coins equal to the sum of numbers written on the chosen panels. Lara quickly made up her mind on how to arrange the stones and was about to start when she noticed an addition to the note in small font below. According to the addition, for the room ceiling not to crush and smash the adventurer, the chosen panels should form a comb. It was explained that the chosen panels form a comb when the sequence *c*_{1}, *c*_{2}, ..., *c*_{n} made from the quantities of panels chosen in each table line satisfies the following property: *c*_{1} > *c*_{2} < *c*_{3} > *c*_{4} < ..., i.e. the inequation mark interchanges between the neighboring elements. Now Lara is bewildered and doesn't know what to do. Help her to determine the largest number of coins she can get and survive at the same time.

Input

The first line contains a pair of integers *n*, *m* (2 ≤ *n*, *m* ≤ 1500). Next *n* lines contain *m* integers each — that is the table itself. The absolute value of the numbers in the table does not exceed 10000.

Output

Print the single number — the maximum number of coins Lara can get.

Examples

Input

2 2

-1 2

1 3

Output

2

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 10:02:00 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|