RUN 国有 $N$ 座城市，其中一些城市之间由双向道路连接。每条道路连接两座不同的城市，且任意两座城市之间最多只有一条道路。并不保证通过现有的道路可以从任意城市到达其他任何城市。

由于交通问题，RUN 的市长决定将所有道路改为单向。改建后，必须满足从任意城市出发，都能通过一条或多条道路到达其他任何城市。为了尽可能节省开支，市长会在所有满足该条件的道路定向方案中，选择总成本最低的一种。注意，定向一条道路的成本取决于具体的道路以及所选的方向。

输入格式

第一行包含一个整数，表示城市数量 $2 \le N \le 18$。

接下来的 $N$ 行，每行包含 $N$ 个以空格分隔的整数。第 $i+1$ 行的第 $j$ 个整数 $a_{ij}$ 表示将道路从城市 $i$ 定向到城市 $j$ 的成本；如果城市 $i$ 和城市 $j$ 之间没有道路，则为 $-1$。

对于所有整数 $1 \le i \le N$，满足 $a_{ii} = -1$。对于所有不同的整数对 $1 \le i, j \le N$，满足 $a_{ij} = a_{ji} = -1$ 或者 $0 \le a_{ij}, a_{ji} \le 10^6$。

输出格式

输出满足市长条件所需的最小定向成本。如果无法满足条件，输出 $-1$。

样例

样例输入 1

4
-1 3 2 -1
3 -1 7 7
5 9 -1 9
-1 6 7 -1

样例输出 1

27

样例输入 2

6
-1 1 2 -1 -1 -1
3 -1 4 -1 -1 -1
5 6 -1 0 -1 -1
-1 -1 0 -1 6 5
-1 -1 -1 4 -1 3
-1 -1 -1 2 1 -1

样例输出 2

-1

说明

对于第一个样例，这是满足市长条件的最廉价道路定向方式：