Hexagonal Tiling

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$

The costs of rhombuses given in example 1

The solution for example 2