Migrated from Lutece 3002 骑手战鹰正在配送您的快递

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

战鹰的直播生涯并不是很理想，于是她兼职送起了快递。 战鹰每天早上需要到取货点取货，接着将所有快递送至配送点，最后再回到自己的家。 我们可以将其中的所有地点视为 $n$ 个点，其中第 $1$ 个点表示取货点，第 $n$ 个点表示战鹰的家，第 $2$ 至 $n-1$ 个点表示快递的配送点。 经过几天的配送，战鹰已经知道从点 $i$ 到点 $j$ 所需要的时间了。由于战鹰还要准备晚上的直播，战鹰想要以最短的时间配送完所有快递并回到家。 目前战鹰已经在取货点了，你能告诉战鹰她最短需要多少时间才能配送完所有快递并回到家吗？

Input

第一行一个整数 $n$ 接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示从点 $i$ 到点 $j$ 需要的时间（记为 $a[i,j]$ ） 对于任意的 $x,y,z$ ，数据保证 $a[x,x]=0$ ， $a[x,y]=a[y,x]$ 并且 $a[x,y]+a[y,z]>=a[x,z]$

Output

一个整数，表示战鹰配送完所有快递并回到家所需要的最短时间

Samples

3
0 5 8 
5 0 3 
8 3 0

8

Constraints

$3 \leq n \leq 20$ $0 \leq a[i,j] \leq 1000000$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming