有一个送外卖的，他手上有$n$份订单，他要把$n$份东西，分别送达$n$个不同的客户的手上。

$n$个不同的客户分别在$1 \cdots n$个编号的城市中。送外卖的从$0$号城市出发，然后$n$个城市都要走一次（一个城市可以走多次），最后还要回到$0$点（他的单位），请问最短时间是多少。

现在已知任意两个城市的直接通路的时间。

输入格式

第一行一个正整数$n$

接下来是一个（$n+1$）$\times$($n+1$)的矩阵，矩阵中的数均为不超过$10000$的正整数。

矩阵的$i$行$j$列表示第$i-1$号城市和$j-1$号城市之间直接通路的时间。

当然城市$a$到城市$b$的直接通路时间和城市$b$到城市$a$的直接通路时间不一定相同，也就是说道路都是单向的。

输出格式

输出最短时间

样例

样例输入

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0

样例输出

8

数据范围与提示

• 对于$50\\%$的数据，$1 \leq n \leq 10$
• 对于$100\\%$的数据，$1 \leq n \leq 15$

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$131072\mathrm{KB}$