题目内容

塔子哥是一名旅游爱好者，他热爱到处游玩，这个寒假也不例外。

他计划前往$n$个城市游玩，这些城市都有着独特的风景和文化。他想要尽可能地省钱，但又不想错过每座城市的精华。为此，他收集了这些城市之间的直达交通费用信息，并打算以最低的花费游览这些城市， $n$ 个城市间的直达交通费由一个二维矩阵表示。

他决定从城市 $0$ 开始出发，然后依次游览其余 $n-1$ 座城市，最后回到城市 $0$。他可以在同一个城市多次停留，以便更好地体验当地的文化和风景。

他非常希望在寒假期间充分利用自己的时间和预算，因此他想要计算出以最低的花费游览所有城市的总费用。

他希望能够为自己的旅游行程做出最佳的规划，让自己的旅游经历充满回忆和意义。

输入描述

第一行一个整数$n$($1 \leq n \leq 15$)

接下来$n$行,每行$n$个整数。代表邻接矩阵, $(1 \leq a_{i,j} \leq 1000)$ , $a_{i,i} = 0$

输出描述

输出一个整数,代表最低花费

样例1

输入

4
0 3 1 2
4 0 2 1
4 1 0 1
2 1 4 0

输出

5