Description

一个美丽的公园，里面总是有很多美丽的景点。

现在有一个公园，里面有 $n$ 个景点，小z想把每个景点都游历一遍，最后从入口离开，入口的编号是 $1$ 。公园不让骑车只能步行，小z也不喜欢走路，所以你要找出那个能在每个景点至少打卡一次、并且走路距离最少的方案。

Input

第一行给出正整数：景点的个数 $N（1<N≤18）$ 。

随后 $N$ 行 $N$ 列，每行给出 $(i,j)$ 景点之间的路径长度 $g_{i,j}$。

其中景点从 $1$ 到 $N$ 编号，$g_{i,j} \le 1000$ 。

Output

输出最小路径长度。

Samples

4
0 25 48 26
25 0 44 33
48 44 0 91
26 33 91 0

151