2189: 自行车送外卖

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:8 Solved:7

Description

       外卖小哥骑自行车从餐厅(0号点)出发,要给 n-1(≤16) 个客户送餐,不需要回到餐厅。给出任意两点之间的骑行时间,问最少需要多少时间完成所有配送?

Input

输入第一行为 n。接着 n行为餐厅(0号点)与每个客户点之间的骑行时间。



Output

输出完成所有配送到最少时间。


Sample Input Copy

4
0 33 12 23
33 0 43 33
12 43 0 44
23 33 44 0

Sample Output Copy

88

HINT

1≤1n≤16,距离数据  <=100