该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

$n$ 个人（编号为 $1$ ~ $n$ ）在做传递物品的游戏。

游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。

即物品只能经过同一个人一次，而且每次传递过程都有一个代价。

求当物品经过所有 $n$ 个人后，整个过程的最小代价是多少。

【输入格式】

第一行一个整数为 $n \ (2 ≤ n ≤ 16)$ 。

下来 $n * n$ 的矩阵，$a_{i,j}$ 表示物品从编号为 $i$ 的人传递到编号为 $j$ 的人所花费的代价，$a_{i,i}$ 等于 -1 （因为物品不能自己传给自己），其他数据均为正整数$(a_{i,j} \le 10^4)$ 。

对于 $50$ 的数据，$n \le 11$ 。

【输出格式】

输出共一个数，为最小的代价总和。

【样例输入】

2
-1 9794
2724 –1

【样例输出】

2724