Description

上帝需要创造一位战士去消灭撒旦，这位战士必须要穿过恶魔城才能与撒旦决斗。恶魔城内有 M 条连接 N 个路口（从 1 到 N 编号）的街道，每一条街道都是 单向的（也就是说你不能逆着该街道指定的方向走），并且在城内无论怎么走都不可能走回原来走过的地方。开始的时候，战士的生命力（HP）为 INITHP、站在１号路口，而撒旦在第 N 号路口等待着他。每一条街道上都有许多魔鬼，但是也有一些街道已经被上帝派去的天使占领了。当战士经过连接 i 号向 j 号路口的街道时，如果占领该街道的是恶魔，那么他的 HP 先加倍然后减少 L[i,j]，我们记为 A[i,j]=-L[i,j]；如果占领该街道的是天使，那么他的 HP 就会 先加倍然后增加 L[i,j]，我们记为 A[i,j]=+L[i,j]；如果该街道不存在，那么A[i,j]=0。如果某一时刻战士的 HP<=0，那么他会死亡。因为这个战士将非常无敌，当他见到撒旦的时候只要还活着，就能一口气把撒旦消灭，所以上帝不希望让他的 INITHP 过高。

Format

Input

给定 N，A[1..N,1..N]，求最小的 INITHP，使这个战士能够活着见到撒旦。

Output

从文件 satanic.in 读入数据，文件第一行有一个正整数 N （3 ≤ N ≤ 100）， 下面跟着的第 i 行第 j 个数为 A[i,j] （绝对值不超过 10000 的整数 ） .

Samples

4
0 -4 0 –10
0 0 +3 0
0 0 0 –14
0 0 0 0

4

Limitation

1s, 1024KiB for each test case.