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 subfield. 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 flowpertime 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 flowpertime which goes from well to sprinkler.
Input
The first line of input contains an integer 1 ≤ N ≤ 1000, the size of field.
The next N lines contains N integers 0 ≤ A_{ij} ≤ 1000, the size of each hose wrapped around.
Output
Output the maximal flowpertime 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:
20171018 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 waterpertime can go around the middle line. 

shubham_001:
20171018 17:53:23
can someone explain examples? 
Added by:  Morass 
Date:  20171016 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 