题目描述

您身处在一个n*n的正方形迷宫中，你在第一行第一列的位置出发，每个格子的迷宫都有相应的费用，每次只能选择下方或者右方的格子，要逃离该房间要支付相应的费用f，其中只有（n,n）格子是出口（也需支付费用）。 问逃出迷宫最少支付的费用是多少？

输入格式

第一行一个正整数 $n$，代表n*n的迷宫。 接下来n行n列，代表每个迷宫格子需要支付的费用。

输出格式

输出一个整数，代表从（n,n）出口逃离最小的费用。

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

31

数据规模与约定

对于 $100\%$ 的数据，$5 \le n \le 30$。 费用$1 \le f \le 9$