问题描述

给定 $n$ 个城市以及它们之间的距离矩阵。 旅行商从 1 号城市出发，需要恰好访问每个城市一次，最后回到 1 号城市。

请你求出最短的旅行路径长度。

输入格式

第一行输入一个整数 $n$。

接下来输入一个 $n\times n$ 的矩阵 $d$，其中 $d_{i,j}$ 表示 $i$ 到 $j$ 的距离，$d_{i,i}=0$。

输出格式

输出一个整数，表示最短旅行路径长度。

样例输入

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

样例输出

80

说明

一种最优路径为：

路径长度为：

评测数据规模

$2\le n\le 8,0\le d_{i,j}\le 100$