32465번 - 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 2ドルN$ 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 2ドルN$ lines of input contains $p_{i,1},p_{i,2},\ldots$.

The next 2ドルN-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 2ドルN-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