Description

阿岳上课要迟到了，但是他现在需要通过一个n ×n 的矩阵才能到达教室。


矩阵中每格数字t_i,j 代表通过所需的时间，若为-1则无法通过。
阿岳现在处于(0,0)的位置，需要通过矩阵的最右下角，即(n-1 ,n-1 )的位置才能到达教室。若只能向下或向右移动，每次移动一格，那么所需最短时间m 为多少?

测试点数据规模

Input Format

第一行 一个整数n  表示矩阵的大小
接下来n行 每行n个整数 t_i,j  表示每格通过所需的时间

Output Format

一个整数m 表示到达教室所需的最短时间

4
 0  1 -1 -1
-1  1  2  3
-1  1 -1  5
 5  2  1  1

7

Source

henaux2302