Description

给定一个整数方阵，在某一列从第一行到最后一行画一条路径，再将路径的两端分别连接左上角元素和右下角元素。请找出从左上角元素到右下角元素的所有路径上数字和的最小值。 例如，一个4*4的方阵为：

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

可以发现，在黄色路径上数字和的最小值为22。

++1	2	3	4++
6	7	8	++1++
5	4	3	++2++
1	3	6	++9++

Input Format

第1行是1个整数n，表示矩阵的行数和列数（2 <= n <= 20）。 接下来的n行为n * n的方阵，其中每行有n个用单个空格隔开的非负整数（0~9）。

Output Format

输出1个个整数，表示矩阵从左上角元素到右下角元素的所有路径上数字和的最小值。

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

22