Even though the prisoners have left the jail cell and landed on Earth, Aggregor was smart enough to capture them back one by one. He successfully absorbs the powers by using Professor Paradox’s time machine and transforming him into a very powerful monster.
Azmuth explains that Aggregor intends to use his new powers in order for the huge trial ahead: collecting the pieces of the Map of Infinity. Hence, Ben and Gwen must stop Aggregor from obtaining the four pieces of the Map of Infinity.
However, Ben and Gwen have failed to stop Aggregor from collecting the first three pieces of the Map of Infinity. The last piece of the map is hidden deep within the Perplexahedron Puzzle. Ben and Gwen have no clue how to get there before Aggregor does and hence asks for your help to navigate their way.
The way to find the last piece of the map is simple.
Each room of the perplexahedron has a number. Everytime you enter a room, that number is added to your score.
You may enter the perplexahedron from any point in the top row and can exit from any point in the bottom row.
You can move downwards, left or right, but you cannot move upwards nor can you visit the same room twice.
If you get the maximum score possible after completing your journey, the last piece of the map of infinity will appear before you.
The first line of the input will be the two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 100). The following n rows each contain m integers representing the perplexahedron matrix. No score will be more than 10000 or less than -10000.
Output the best possible total score that can be obtained.
Sample Input 1
4 4
2 0 -3 4
1 0 -2 -6
3 -7 12 4
-1 8 -1 2
Sample Output 1
27
Explanation
The best amount can be obtained by starting from the top right corner. The route is left left left down right right down right down left left.