给你一个边长为 $N$ 的正六边形。一个正六边形可以分割成若干个边长为 $1$ 的单位正三角形，如下图所示。我们将用边长为 $1$ 的单位菱形（由两个共边的单位正三角形拼接而成）来完全覆盖这个六边形。

由三角形组成的六边形

对于每个可以放置单位菱形的位置，都给出了放置该菱形的代价。请找出覆盖整个六边形所需的最小总代价。

输入格式

第一行包含一个整数 $N$。

接下来的 $2N$ 行包含在各行内部放置菱形的代价。 设在第 $i$ 行中，由拼接第 $j$ 个和第 $j + 1$ 个三角形形成的菱形的代价为 $p_{i,j}$。 这 $2N$ 行中的第 $i$ 行包含 $p_{i,1}, p_{i,2}, \dots$。

接下来的 $2N - 1$ 行包含跨越两行放置的菱形的代价。 设由拼接第 $i$ 行的第 $j$ 个倒三角形和其上方相邻的三角形形成的菱形的代价为 $q_{i,j}$。 这 $2N - 1$ 行中的第 $i$ 行包含 $q_{i+1,1}, q_{i+1,2}, \dots$。

输出格式

输出使用单位菱形完全覆盖六边形所需的最小代价。可以证明，总是存在一种使用单位菱形覆盖六边形的方法。

数据范围

• $1 \le N \le 100$
• $0 \le p_{i,j}, q_{i,j} \le 10^9$

样例

输入样例 1

1
2 3
4 5
1 6

输出样例 1

9

输入样例 2

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

输出样例 2

58

说明

样例 1 中给出的菱形代价

样例 2 的解