Description

给定一个n*n的网格，每个网格上都有一个值，请找出一条从左上角到右下角的路径，使得路径上的数字总和最小。每次只能向下或者向右移动一步

Format

Input

多组输入

每组输入第一行一个n，

输入$n*n$行的矩阵，

$n<=100$;

$0<=矩阵值<=1000$

Output

一行输出一个数字，代表一组的输出结果

Samples

3
1 3 1
1 5 1
4 2 1
5
1  4  6  8  10
2  5  7  15 17
6  8  9  18 20
10 11 12 19 21
20 23 25 29 33

7
109

Hints

sb题