题目描述

$n$ 个人在做传递物品的游戏,编号为 $1 \sim n$。

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

即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；

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

输入格式

第一行为 $n$ ,表示共有 $n$ 个人（$2 \le n \le 16$）；

以下为 $n \times n$ 的矩阵，第 $i+1$ 行、第 $j$ 列表示物品从编号为 $i$ 的人传递到编号为$j$ 的人所花费的代价，特别的有第 $i+1$ 行、第 $i$ 列为 $-1$（因为物品不能自己传给自己），其他数据均为正整数且 $\le 10000$。

输出格式

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

样例

2
-1 9794
2724 –1

2724

说明/提示

对于50%的数据，$n \le 11$；
对于100%的数据，$2 \le n \le 16$