問題文

$N$ 台のゲーム機がある。ゲーム機 $i,j(1 \leq i,j \leq N,i \neq j)$ について、ゲーム機 $i$ からゲーム機 $j$ までの送信時間は $T_{i,j}$ 秒である。 このゲーム機同士の通信はP2P方式を採用しており、$N$ 台の内の1台のゲーム機を親機、残りのゲーム機を子機としたとき、子機から親機にコマンド入力が送信され、その後親機から子機にその結果が送信されることによってゲームの通信プレイが成立している。 ここで、ゲームの通信プレイを快適に行うためには、なるべく子機から親機までの送信速度と親機から子機までの受信速度の両方が早くなければならないため、適切に親機を選ばなければならない。具体的には、残りの全ての子機のうち、最も親機への送信時間がかかるものの送信時間と、最も親機からの受信時間がかかるものの親機からの受信時間とを足し合わせた和が最も小さくなるような親機となるゲーム機はどれかを選ばなければならない。ただし、親機への送信と親機からの受信において、他の子機を経由することもできる。 適切に親機を選んだ際、残りの全ての子機のうち、最も親機への送信時間がかかるものの送信時間と、最も親機からの受信時間がかかるものの受信時間とを足し合わせた和を求めよ。

制約

• $3 \leq N \leq 100$
• $1 \leq T_{i,j} \leq 10^9$
• $T_{i,i} = 0$

入力

入力はすべて整数である。

N
T_{1,1} T_{1,2} .. T_{1,N}
T_{2,1} T_{2,2} .. T_{2,N}
...
T_{N,1} T_{N,2} .. T_{N,N}

出力

適切に親機を選んだ際、残りの全ての子機のうち、最も親機への送信時間がかかるものの送信時間と、最も親機からの受信時間がかかるものの受信時間とを足し合わせた和を求めよ。

サンプル

3
0 2 3
1 0 5
10 10 0

13

ゲーム機$1$を親機とすると、最も親機への送信時間がかかるものはゲーム機$3$であり、$10$秒かかります。また、最も親機からの受信時間がかかるものもゲーム機$3$であり、$3$秒かかります。よって足し合わせた和は$13$秒です。和を$13$秒より小さくすることはできないので、$13$を出力します。

4
0 100 1 100
100 0 1 100
1 1 0 1
100 100 1 0

2