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

题目背景

在魔幻草原深处，有一个由 $n$ 个神秘草场环绕组成的“幻影羊圈”。噜噜想要带着她的小羊，从 $1$ 号草场出发，恰好游历每个草场一次，再回到起点，搜集草场中的魔法露珠。每两座草场之间都有一条通路，需要消耗一定魔力。

问题描述

给定草场数量 $n$ （编号 $1\ldots n$）和一张 $n\times n$ 的魔力消耗矩阵 $\mathrm{cost}$，其中

$$\mathrm{cost}[i][j] \;=\; \text{从草场 }i\text{ 走到草场 }j\text{ 所需的魔力（非负整数）}, $$

且对于所有 $1\le i\le n$ 有 $\mathrm{cost}[i][i]=0$。请计算一条环形巡游路线，要求：

1. 从 $1$ 号草场出发；
2. 恰好经过每个草场一次；
3. 回到 $1$ 号草场；

使得全程魔力消耗总和最小。

输入格式

第一行：整数 $n$。

接下来的 $n$ 行，每行 $n$ 个非负整数。第 $i$ 行第 $j$ 列为 $cost[i][j]$。

输出格式

一个整数，表示最小的魔力消耗总和。

样例

5
0 29 20 21 16
29 0 15 17 28
20 15 0 18 23
21 17 18 0 25
16 28 23 25 0

92

样例解释

将草场编号映射为 $1,2,3,4,5$ 后，消耗矩阵为：

$$\mathrm{cost} \;=\; \begin{pmatrix} 0 &29 &20 &21 &16\\ 29 &0 &15 &17 &28\\ 20 &15 &0 &18 &23\\ 21 &17 &18 &0 &25\\ 16 &28 &23 &25 &0 \end{pmatrix} $$

最优的环形巡游路线之一是

$$1 \;\to\; 4 \;\to\; 2 \;\to\; 3 \;\to\; 5 \;\to\; 1 $$

对应的魔力消耗依次为：

$$\mathrm{cost}[1][4] \;+\;\mathrm{cost}[4][2] \;+\;\mathrm{cost}[2][3] \;+\;\mathrm{cost}[3][5] \;+\;\mathrm{cost}[5][1] \;=\;21 + 17 + 15 + 23 + 16 \;=\;92. $$

因此，样例的最小总消耗为 92。

数据范围与子任务

对于所有数据，保证：$1 \le n \le 15$。

数据保证随机生成。

子任务划分

子任务编号	条件限制	分值
子任务一	$1 \le n \le 10$	$30\%$
子任务二	$1 \le n \le 12$
子任务三	$1 \le n \le 15$	$40\%$