实况足球之传球

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

   巴塞罗那队夺得了去年西甲联赛和欧洲冠军杯的冠军,以雄厚的实力登顶欧洲球队的巅峰。当然,谈到巴萨的踢球风格,熟悉它的球迷都会想到一个词:传球。确实,巴萨的打法是控球流,具体实现就是无限的精巧传球配合,这样的打法往往让对方感到无奈甚至绝望,直到足球进入对方的球门。

    我们知道足球场上位置是非常重要的,每个人必须要负责好自己的位置,虽然有时候可以灵活的变动,但多数时间内每个人都是在自己的位置上的,这样才能更有效地实施教练的战术策略而不会慌乱。大体上的位置分为四个部分,门将是必不可少的,往前是后卫,再往前是中场,顶在最前面的是前锋。

       传球的目标一方面是消耗对方的意志,最主要的方面是寻找机会组织进攻,给对方致命一击。我们规定每一次传球对整次进攻都会有一个成功指数,从门将到后卫,再中场,最后到前锋,形成射门,会有一个总的成功指数。这个总的成功指数是多个传球成功指数的和。


虽然每个人都希望得到成功指数的最大值,但是巴萨教练瓜迪奥拉希望找出球员们的传球路线中总成功指数的最小值,从而可以进行调整,从而提高整个队伍传球组织进攻的成功率。但是他不会编程,所以他找到了你——一个ACMer,希望你能帮他写一个计算总成功指数最小值的程序,能够快速的计算他想要的值。


   瓜迪奥拉提供给你的数据包含从门将巴尔德斯到前锋梅西的每个球员的传球路线,即每个球员会将自己脚底下的求传给哪几个球员以及传给每个人的成功指数。

 

Input

   输入数据有多组,处理到文件结束。每组数据第一行是一个正整数N (N < 12)表示本次比赛场上球员的总数,接下来是一个N*N的矩阵。矩阵中第ij个元素表示足球从第i个球员传到第j个球员的成功指数。矩阵中每个元素为100以内的整数。

Output

   每组数据输出一行,即本球队的传球的从1号球员到N号球员的总成功指数的最小值。

Sample Input

11
0 3 7 4 3 8 0 8 8 0 6
8 0 1 9 8 9 7 2 2 8 2
8 9 0 0 7 8 1 5 8 6 1
2 4 2 0 5 8 6 2 6 5 3
9 2 4 6 0 1 8 2 1 1 9
7 6 2 9 5 0 2 0 0 3 9
1 8 1 9 5 3 0 2 5 2 5
8 6 7 7 2 2 9 0 4 1 9
6 9 8 2 5 5 4 9 0 1 2
5 0 8 3 9 3 9 6 7 0 9
9 7 6 9 3 5 7 6 6 5 0
9
0 7 4 0 9 4 8 8 2
4 0 5 5 1 7 1 1 5
2 7 0 6 1 4 2 3 2
2 1 6 0 8 5 7 6 1
8 9 2 7 0 9 5 4 3
1 2 3 3 4 0 1 1 3
8 7 4 2 7 7 0 9 3
1 9 8 6 5 0 2 0 8
6 0 2 4 8 6 5 0 0

Sample Output

2
1

Hint


Source

tongjiantao