问题描述

给定一张 $n$ 个结点带权无向图，点从 $0 \sim n - 1$ 标号，求从起点 $0$ 出发，经过每一个点有且只有一次后再回到起点的最短路。

输入格式

第一行输入整数 $n$。$(1\le n\le 20)$

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $a_{i, j}$）。$(1\le a_{i,j}\le 10^6)$

数据保证当 $i=i$ 时 $a_{i,i}=0$，但可能 $a_{i,j}\ne a_{j,i}$

输出格式

输出从起点 $0$ 出发，经过每一个点有且只有一次后再回到起点的最短路。

样例输入

3
0 2 3
2 0 4
3 3 0

样例输出

8

说明

$[1,3,2,1]$ 是路程最短的顺序。