LCC/Moose '19 Contest 1 S2 - Siege

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Darbian is speedrunning a game that requires him to lay siege on a castle. The castle is in the shape of a square with N 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 N (1 \le N \le 100), the number of walls around the castle. The next 2N lines each contain 2N 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

There are no comments at the moment.