Thug Ralph has been living in a slot machine for 30 years, and you can see him on the screen of that machine.
Today, Ralph is walking around a screen that displays a rectangular image divided into N x N cells. In each cage there is a plate with his favorite pancakes & nbsp; (all plates have a different number of pancakes). Ralph starts moving from the lower left cell of the rectangle. After eating all the pancakes in the current cell, he moves one cell to the right or one cell up, always choosing the cell with more pancakes in the plate (there are no plates with pancakes outside the rectangle ). Eventually Ralph comes to the top right cell. You also have to determine how many pancakes Ralph ate while traveling around the screen. Ralph also ate pancakes in the initial and final cages with great pleasure.
Input
The program receives an integer as input in the first line N – image size (2 <= N <= 10). The following N lines set space-separated numbers denoting the number of pancakes on the plates, starting from the top row and ending with the bottom one. All numbers – various, natural, not exceeding 100.
Output
Print one number - the number of pancakes that Ralph will eat when he gets to the top right cell.
Examples
| # |
Input |
Output |
| 1 |
2
37 82
23 52
|
157
|