题目描述

学校组织同学们参观一座科技馆。科技馆中有 $n$ 个需要参观的展厅，编号为 $1,2,\ldots,n$。入口大厅编号为 $0$。

参观路线需要满足：

• 从入口大厅 $0$ 出发；
• 每个展厅 $1$ 到 $n$ 都必须参观且只需参观一次；
• 参观完所有展厅后，回到入口大厅 $0$。

已知任意两个地点之间的路程 $d_{i,j}$，其中 $0 \le i,j \le n$。

请你求出完成整次参观所需的最短总路程。

输入格式

第一行输入一个整数 $n$，表示需要参观的展厅数量。

接下来 $n+1$ 行，每行输入 $n+1$ 个整数。

第 $i+1$ 行的第 $j+1$ 个整数表示 $d_{i,j}$，即从地点 $i$ 到地点 $j$ 的路程。

输出格式

输出一个整数，表示从入口大厅出发，参观完所有展厅并回到入口大厅的最短总路程。

样例

3
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80

2
0 5 9
6 0 4
3 8 0

12

样例1解释

一种最优路线为：

0 -> 1 -> 3 -> 2 -> 0

总路程为：

可以证明不存在总路程更短的参观路线。

数据范围

对于 $100\%$ 的数据，满足 $1 \le n \le 9$，$0 \le d_{i,j} \le 10^6$，$d_{i,i}=0$。