ADAHOSE - Ada and Hose


As you might already know, Ada the Ladybug is a farmer. She owns a square field. There is a hose wrapped around each 1x1 sub-field. All hoses are additionally combined into a bigger hose everywhere where they touch (so the water can arbitrarily flow between both of them [or even all four of them]). Each hose has its own flow-per-time attribute.

There is a big well (an infinite source of water) above the field and a big sprinkler under the field. Additionally very big hoses (for our case we can consider them infinetly big) are lead from well to top of the field and from bottom to the sprinkler. Your quest is simple: Calculate tha maximal total flow-per-time which goes from well to sprinkler.

Field

Input

The first line of input contains an integer 1 ≤ N ≤ 1000, the size of field.

The next N lines contains N integers 0 ≤ Aij ≤ 1000, the size of each hose wrapped around.

Output

Output the maximal flow-per-time achievable.

Example Input

3
9 3 2
1 9 3
3 3 9

Example Output

26

Example Input 1

4
2 0 0 2
0 2 2 0
2 0 0 2
0 2 2 0

Example Output 1

8

Example Input 2

8
2 2 0 1 2 1 5 1
5 1 3 7 1 6 3 1
3 8 5 3 6 6 8 8
2 9 6 6 8 2 3 0
5 4 3 9 7 1 0 4
2 5 1 5 2 5 6 5
5 3 8 3 9 8 1 1
8 9 0 8 2 3 1 9

Example Output 2

28

hide comments
morass: 2017-10-18 23:12:36

@shubham_001: For example the first exmple shall be same as on picture. You simply flow from the star (upper one) to the bottom star. As you can see, no more than 26 water-per-time can go around the middle line.

shubham_001: 2017-10-18 17:53:23

can someone explain examples?


Added by:Morass
Date:2017-10-16
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All