Description

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

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