题目描述

某镇有 $n$ 个村庄，编号为 $1, 2, \dots, n$。一位售货员需要从 $1$ 号村庄的商店出发，到每个村庄恰好售货一次，最后返回 $1$ 号村庄。

已知村庄 $i$ 到村庄 $j$ 的单向路程为 $s_{i,j}$（注意 $s_{i,j}$ 与 $s_{j,i}$ 通常不同）。

请找出一条总路程最短的巡回路线。

输入格式

第一行一个整数 $n$，表示村庄数。

接下来 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个整数表示 $i$ 到 $j$ 的单向路程 $s_{i,j}$。

输出格式

一行一个整数，表示最短的总路程。

样例

3
0 2 1
1 0 2
2 1 0

3

提示

对于全部数据，$2 \le n \le 20$，$1 \le s_{i,j} \lt 10^3$。