#DP0602. 旅行商

旅行商

题目描述

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

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

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

输入格式

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

接下来 nn 行,每行 nn 个整数。第 ii 行第 jj 列的整数表示 ai,ja_{i,j}

输出格式

一行一个整数表示答案。

Samples

2
0 1
2 0
3

数据范围

对于100% 的数据,2n182≤n≤18,如果 i=ji=j,则 ai,j=0a_{i,j}=0,否则 1ai,j100001≤a_{i,j}≤10000