Darbian is speedrunning a game that requires him to lay siege on a castle. The castle is in the shape of a square with walls wrapping around it. Each wall is broken into sections of different heights.
Darbian sieges the castle by repeatedly picking a section of the outermost unbreached wall and scaling that section, which takes time equal to the height of the section. Once he reaches the top, the wall is considered breached, and he can immediately move onto breaching the next wall. Darbian's siege is victorious once all the walls are breached.
Help Darbian determine the minimum time required to siege the castle.
Input Specification
The first line of input contains an integer (), the number of walls around the castle. The next lines each contain positive integers less than or equal to 1,000, the height of a wall section. A single wall consists of all the sections in a square centered in the middle of the castle.
Output Specification
Output the minimum number of time it will take to siege the castle.
Sample Input 1
3
3 1 1 1 1 3
1 4 2 2 4 1
1 2 3 3 2 1
1 2 3 3 2 1
1 4 2 2 4 1
3 1 1 1 1 3
Sample Output 1
6
Explanation of Sample Input
Darbian can breach the outer wall at one of the sections of height 1; the middle wall at one of the sections of height 2; and the inner wall at any of the sections of height 3, for a total time of 6.
Comments