Description

YT City is a well-planned city, divided into $n \times n$ regions by east-west and north-south main roads. For simplicity, YT City can be viewed as a square, and each region can also be viewed as a square. Thus, YT City contains $(n+1) \times (n+1)$ intersections and $2n(n+1)$ two-way roads (referred to as roads), where each two-way road connects two adjacent intersections on the main roads. The figure below shows a map of YT City ($n=2$), where the city is divided into $2 \times 2$ regions, containing $3 \times 3$ intersections and 12 two-way roads.

As the mayor of the city, Xiao Z has obtained statistics on the traffic flow in both directions on every road in YT City during the morning rush hour, which is the number of people passing through the road in that direction during the rush hour. Each intersection has a different altitude value. The city of YT considers climbing to be a very tiring task; climbing an altitude of $h$ requires consuming $h$ units of physical energy. If it is downhill, no physical energy is consumed. Therefore, if the altitude of the destination of a road minus the altitude of the starting point is $h$ (where $h$ can be negative), the physical energy consumed by a person passing through this road is $\max\{0, h\}$ (where $\max\{a, b\}$ denotes the larger of the two values $a$ and $b$).

Xiao Z also measured that the altitude of the intersection at the northwest corner of the city is $0$, and the altitude of the intersection at the southeast corner is $1$ (as shown in the figure above), but the altitudes of other intersections are unknown. Xiao Z wants to know the minimum total physical energy consumed by people climbing during the morning rush hour under the ideal situation (i.e., you can arbitrarily assume the altitudes of other intersections).

Input

The first line contains an integer $n$, with the meaning as described above.

The next $4n(n+1)$ lines each contain a non-negative integer, representing the traffic flow information for one direction of one road. The input order is: $n(n+1)$ values representing the traffic flow from west to east, then $n(n+1)$ values representing the traffic flow from north to south, $n(n+1)$ values representing the traffic flow from east to west, and finally $n(n+1)$ values representing the traffic flow from south to north. For each direction, the input order is given from north to south, and if the north-south position is the same, from west to east (see the example input).

Output

The output contains a single integer, representing the minimum total physical energy consumed by people climbing during the morning rush hour under the ideal situation (i.e., the minimum value of the total physical energy), rounded to the nearest integer.

Examples

Input 1

1
1
2
3
4
5
6
7
8

Output 1

3

Note

The example data is shown in the figure below.

The altitudes in the ideal situation are as shown in the figure above.

Constraints

• For 20% of the data: $n \le 3$;
• For 50% of the data: $n \le 15$;
• For 80% of the data: $n \le 40$;
• For 100% of the data: $1 \le n \le 500$, $0 \le \text{flow} \le 1,000,000$, and all flows are integers.

Note

Altitude values are not necessarily integers.