问题描述

某乡有 $n$ 个村庄（编号 $1 \sim n$），商店位于村庄 $1$。

有一名售货员，他需要从商店出发，访问每个村庄恰好一次，并最终回到村庄 $1$。

已知任意两个村庄之间的单向路程 $s_{i,j}$ 是已知的，且不一定满足对称性，即 $s_{i,j} \ne s_{j,i}$ 也可能成立。

请你帮助售货员规划一条访问所有村庄并回到起点的路线，使得总路程最短，并输出该最短距离。

输入格式

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

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数表示从村庄 $i$ 到村庄 $j$ 的距离 $s_{i,j}$。

输出格式

输出一个整数，表示完成一次完整旅行（从 $1$ 出发，访问所有村庄恰好一次并回到 $1$）的最短路程。

样例输入

3
0 2 1
1 0 2
2 1 0

样例输出

3

数据范围

对于 $30\%$ 的数据，保证 $n \le 8$。

对于 $100\%$ 的数据，保证 $2 \le n \le 20$，$1 \le s_{i,j} < 10^3$。