J16 例题-4 最低通行费

题目描述

佩奇准备穿过一个 $N*N$ 的正方形的网格，去参加一个非常重要的游园活动。要从网格的左上角进，右下角出。每次穿越只能向下或者向右走一步，而在经过每个小方格时，都需要缴纳一定的费用。佩奇期望用最少费用穿越出去。请问至少需要多少费用？

输入格式

第一行一个整数 $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

样例分析

最小值为 $109 =1+2+5+7+9+12+19+21+33$ 。

数据范围

对于 $100\%$ 的数据，有 $1 \leq n \leq 100$。