아즈텍의 섬

문제

로터스는 농부 존에게서 조그만 섬을 샀다. 이 섬은 아래 그림의 주황색 영역과 같이 한 변의 길이가 $n$인 계단 모양의 도형을 붙여둔 Aztec diamond 모양이다. $n$은 짝수로, 아래 그림은 $n = 6$인 경우이다.

이 섬 위의 격자점에는 농사를 지을 밭이 있다. 위 그림에서 밭이 있는 점은 빨간 점이나 파란 점으로 표시되어 있다. 파란 점은 $x + y$가 홀수인 점 $(x, y)$들로, 이 섬의 특산물이 생산되는 중요한 밭이 위치해 있다. 좌표축을 따라 난 길들은 물길이 날 수 있는 자리로, 농사를 짓기 위해서 이 길 중 몇 개를 수로로 만들어야 한다. 농사를 성공적으로 짓기 위한 조건은 다음과 같다.

• 모든 밭에 물이 들어와야 하므로, 각각의 밭에는 섬의 경계와 연결된 수로가 존재해야 한다.

• 파란 점은 특별히 관리해야 하는 점으로, 이 점에는 두 개 이상의 수로가 연결되어 있어야 한다.

그런데 수로마다 토목 공사 비용이 각기 다를 수 있다. 따라서 위의 두 조건을 모두 만족하면서 토목 공사의 비용을 최소화해야 한다. 바쁜 로터스를 도와 토목 공사에 드는 비용의 최솟값을 알려주도록 하자.

입력

입력의 첫 줄에 영토의 크기를 나타내는 정수 $n$이 주어진다.

이후 $2n-1$개의 줄에 걸쳐 $x$축에 평행한 방향의 경계선, 즉 가로로 난 길들의 토목 공사 비용이 주어진다. $h_{x,y}$를 $(x, y)$와 $(x+1, y)$를 잇는 가로줄의 공사 비용이라고 할 때, $y$번째 줄에는 $h_{x, n - y}$가 $x$가 증가하는 순서대로 주어진다. $(1 \le y \le 2n-1)$ 줄마다 주어지는 입력의 개수는 $2$개. $4$개, $\cdots$ $2n-2$개, $2n$개, $2n-2$개, $\cdots$, $4$개, $2$개임에 주목하라.

이후 $2n-1$개의 줄에 걸쳐 세로로 난 길들의 토목 공사 비용이 주어진다. $v_{x, y}$를 $(x, y)$와 $(x, y-1)$을 잇는 길의 공사 비용이라고 할 때, $x$번째 줄에는 $v_{-n + x, y}$가 $y$가 감소하는 순서대로 주어진다. $(1 \le x \le 2n-1)$

$h_{x, y}, v_{x, y}$는 모두 양의 정수이다.

출력

첫째 줄에 공사 비용의 최솟값을 출력한다.

제한

• $2 \le n \le 8$, $n$은 짝수.

• $1 \le h_{x,y}, v_{x,y} \le 10^{8}$

2
3 1
4 1 5 9
2 6
5 3
5 8 9 7
9 3

24

출처

• 문제를 만든 사람: TAMREF

• 문제를 검수한 사람: aeren