题目描述

光头强的世界里有 $n$ 个城市，城市两两之间通过高速公路连接，从第 $i$ 个城市走到第 $j$ 个城市需要花费 $a_{i,j}$ 的时间。

现在光头强想从 $1$ 号城市出发旅游，他想把每个城市都玩个遍，但又不想在一个城市玩两遍，玩完以后光头强需要回到 $1$ 号城市应付期末考试。请问光头强最少需要花费多少时间？

光头强到了一个城市以后，一定会在这个城市游玩。光头强在出发之前会先在 $1$ 号城市游玩。连接两个城市的高速公路不会经过其他城市。由于路况的原因，从第 $i$ 个城市走到第 $j$ 个城市花费的时间不一定等于从第 $j$ 个城市走到第 $i$ 个城市花费的时间。

输入格式

第一行一个整数 $n$ 表示城市数目。

接下来 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 列的整数表示 $a_{i,j}$。

输出格式

一行一个整数表示答案。

Samples

2
0 1
2 0

3

数据范围

对于100% 的数据，$2≤n≤18$，如果 $i=j$，则 $a_{i,j}=0$，否则 $1≤a_{i,j}≤10000$。