E. Hexagonal Tiling
time limit per test
4 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

You are given a regular hexagon having sides of length $$$N$$$. A regular hexagon can be split into unit equilateral triangles of side length $$$1$$$ as shown in the figure below. We are going to completely fill the hexagon with unit rhombuses of side length $$$1$$$ formed by joining two equilateral triangles which share an edge.

Hexagon formed from triangles

For each position a unit rhombus can be placed, the cost of placing a rhombus is given. Find the minimum cost required to fill the hexagon.

Input

The first line of input contains $$$N$$$.

The following $$$2N$$$ lines contain the cost for a rhombus placed in each respective row.

Let's say the cost of a rhombus formed by joining the $$$j$$$-th and $$$j+1$$$-th triangles of the $$$i$$$-th row is $$$p_{i, j}$$$.

The $$$i$$$-th of the $$$2N$$$ lines of input contains $$$p_{i, 1}, p_{i, 2}, \ldots$$$.

The next $$$2N-1$$$ lines of input contain the cost for a rhombus placed across two rows.

Let's say the cost of a rhombus formed by joining the $$$j$$$-th inverted triangle of the $$$i$$$-th row and the triangle above it is $$$q_{i, j}$$$.

The $$$i$$$-th of the $$$2N-1$$$ lines contains $$$q_{i+1, 1}, q_{i+1, 2}, \ldots$$$.

Output

Print the minimum cost required to fill the hexagon using unit rhombuses. It can be proved that it is always possible to fill a hexagon using unit rhombuses.

Scoring
  • $$$1 \leq N \leq 100$$$
  • $$$0 \leq p_{i, j}, q_{i, j} \leq 10^9$$$
Examples
Input
1
2 3
4 5
1 6
Output
9
Input
2
3 14 15 9
2 6 5 3 5 8
97 9 3 2 3 8
4 6 26 4
3 3 8
3 2 7 9
5 0 2
Output
58
Note
The costs of rhombuses given in example 1
The solution for example 2