Description

一个n行n列的网格，表示魔塔，魔塔的每个格子中有一个怪物或者一瓶药水，一名勇士，有初始体力值，从魔塔左上角入口的格子进入，到右下角出口的位置夺取宝石，夺取宝石的规则如下：

1.勇士只能从魔塔内走到右下角且每次只能向下或向右走一格。

2.怪物格子中有一个负整数，表示勇士进入该格子后，会损失对应体力值，药水格子中有一个正整数，表示勇士进入该格子后，增加对应体力值。

3. 夺取宝石全程，勇士须保持体力值大于0，否则夺取宝石失败。

给定n行n列的魔塔，计算勇士最少需要多少初始体力值才能成功夺取宝石。

按照-1，2，-4，2，-2的路线，当勇士初始体力值为4时：

Input Format

第一行输入一个整数n(2<=n<=200),表示魔塔的行数和列数

接下来输入n行，每行n个整数（-1000<=整数<=1000，不能为0），其中负数表示会损失的体力值，正数表示会增加的体力值，整数之间以一个空格隔开

Output Format

一个整数，表示勇士最少需要的初始体力值

3
-1 1 -6
2 -4 1
-5 2 -2

4

Source