Optimizing Uphill Exertion in YT City

In the well‐planned YT City, the urban area is divided by east–west and north–south main roads into \(n \times n\) square regions. Consequently, there are \((n+1)\times(n+1)\) intersections and \(2n\times(n+1)\) bidirectional roads. Each road connects two adjacent intersections. During the morning rush hour, the number of people traversing each road in each direction is recorded.

Each intersection is assigned an altitude. Citizens feel that climbing is tiring – for every upward move of \(h\) in altitude, a person spends \(h\) units of energy, while downhill incurs no cost. That is, if a road goes from an intersection with altitude \(a\) to one with altitude \(b\), the effort required (per person) is \(\max\{0, b-a\}\).

The mayor knows that the intersection at the northwest corner has an altitude of \(0\) and the intersection at the southeast corner has an altitude of \(1\). The altitudes of the other intersections can be chosen arbitrarily. What is the minimum total uphill effort (summed over all people on all roads) that could possibly result during the rush hour if the altitudes (except for the two fixed intersections) are optimally assigned?

Hint: By assigning altitudes of 0 to one part and 1 to the other, this problem reduces to finding a directed s-t minimum cut in a network where each road from intersection \(u\) to \(v\) has a capacity equal to the number of people moving along that direction.

inputFormat

The input begins with an integer \(n\) representing the number of regions per side.

Then, there are \((n+1)\) lines for the horizontal roads. Each of these lines contains \(2n\) integers. For each adjacent pair of intersections in that row, the first integer is the flow from left to right and the second is the flow from right to left.

After that, there are \(n\) lines for the vertical roads. Each of these lines contains \(2(n+1)\) integers. For each column in that segment (connecting row \(i\) and row \(i+1\)), the first integer is the flow from top to bottom and the second is the flow from bottom to top.

It is guaranteed that all numbers are nonnegative integers.

outputFormat

Output a single integer, the minimum total uphill effort during the morning rush hour.

sample

2
1 2 3 4
2 1 4 3
3 3 2 2
1 1 2 2 3 3
3 2 1 1 2 1

2