Nlogonia 以其稳健的道路基础设施而闻名。该国共有 $N$ 座城市，编号从 $1$ 到 $N$。对于每一对不同的城市 $i$ 和 $j$，它们之间都有一条长度为 $L_{i,j}$ 的双向道路。

Nlogonia 的市民们非常兴奋，因为音乐剧《汉密尔顿》（Hamilton）首次来到该国演出。演出组织方希望让每一位市民都有机会观看音乐剧，因此他们想要选择一条恰好访问每座城市一次的路径。这样的路径是 $N$ 座城市的一个排列 $P_1, P_2, \dots, P_N$，其总长度为 $\sum_{i=1}^{N-1} L_{P_i, P_{i+1}}$。

组织方担心，如果让演员选择路径，他们将不得不花费大量的燃油费。但他们也担心，如果不让演员做任何选择，演员会失去动力，从而在舞台上表现不佳。因此，组织方允许演员选择路径中偶数位置的城市，即演员可以选择城市 $P_2, P_4, \dots, P_{2 \cdot \lfloor N/2 \rfloor}$。

经过多次商议，演员们做出了他们的选择。与人们对这群富有创造力的人的预期相反，他们达成了一个相当无聊的结果，并决定偶数位置应由与索引标识符相同的城市占据，即对于所有偶数 $i$，都有 $P_i = i$。

现在组织方需要你的帮助。你能确定满足演员决定的路径的最小总长度吗？

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 500$)，表示 Nlogonia 的城市数量。接下来的 $N$ 行，每行包含 $N$ 个整数，表示城市之间的道路长度。第 $i$ 行的第 $j$ 个整数是 $L_{i,j}$ ($1 \le L_{i,j} = L_{j,i} \le 10^9$，其中 $i=1, 2, \dots, N$，$j=1, 2, \dots, N$ 且 $i \neq j$)，表示城市 $i$ 和 $j$ 之间双向道路的长度。如果 $i = j$，则 $L_{i,j} = 0$，因为城市到自身没有实际道路。

输出格式

输出一行，包含一个整数，表示满足演员决定且恰好访问每座城市一次的路径的最小总长度。

样例

样例输入 1

4
0 3 2 13
3 0 8 9
2 8 0 5
13 9 5 0

样例输出 1

16