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.
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$$$.
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.
- $$$1 \leq N \leq 100$$$
- $$$0 \leq p_{i, j}, q_{i, j} \leq 10^9$$$
12 34 51 6
9
23 14 15 92 6 5 3 5 897 9 3 2 3 84 6 26 43 3 83 2 7 95 0 2
58
The costs of rhombuses given in example 1 
The solution for example 2
