题目描述

一个商人要穿过N×N的网格，从左上角进入，从右下角离开。经过每个格子都需要1个单位时间，并缴纳该格子的费用，起点和终点也计时、收费。

商人必须在2N-1个单位时间内通过，只能上下左右移动，不能离开网格。求最少需要支付多少费用。

输入格式

第一行整数N。接下来N行，每行N个整数，表示各格子的费用。

输出格式

输出最少需要支付的总费用。

样例

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

109

数据范围

1≤N<100；每个格子的费用是0至100的整数。