I want pizza, and more...#1299
Michelangelo, like all his Ninja Turtle brothers, loved pizza very much. That is why he eagerly awaited the moment when he could start collecting pizza from the pizzeria grid. However, this day brought several problems, mainly because the pizza chef did not like it when the turtle took too much pizza...
To let the chef continue to make pizza in the future and minimize the trouble, as well as to avoid angering the chef too much himself (i.e., the turtle never passes twice over the same pizzeria cell from which pizza has already been collected), Michelangelo always starts collecting pizza from the upper left corner of the pizzeria and moves only right and down until reaching the bottom right box. Then, he returns to the starting point, moving only left and up.
Help Michelangelo find a route that will allow him to collect the largest possible amount of his favorite treat.
The input data contains several test cases. Each test case begins with a line indicating the number of pizza boxes in the pizzeria (1 < N \leq 600). The following lines of each test case contain the number of pizza slices that the turtle can take from the box located at that position in the pizzeria. It is known that each pizza box could not contain more than slices.
For each test case, output the optimal number of pizza slices Michelangelo can collect.
Example 1