题目描述

有 $n$ 座城市，编号为 $1$ 到 $n$。任意两座不同城市 $i,j$ 之间都存在一条从 $i$ 到 $j$ 的单向道路，通行费用为 $c_{i,j}$。 一名旅行商从 $1$ 号城市出发，需要恰好访问每座城市一次，最后回到 $1$ 号城市。 注意，$c_{i,j}$ 与 $c_{j,i}$ 不一定相等。

请求出完成这次旅行的最小总费用。

输入格式

第一行输入一个整数 $n$，表示城市数量。

接下来 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个整数为 $c_{i,j}$，表示从 $i$ 号城市到 $j$ 号城市的通行费用。

保证 $c_{i,i}=0$，且当 $i\ne j$ 时 $1\le c_{i,j}\le10^9$。

输出格式

输出一个整数，表示最小总费用。

样例

样例 1

输入：

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

输出：

35

数据范围