UOJ Logo FLYIOI UOJ

FLYIOI

#31. 最小伤害

问题描述

把儿站在一个N x N的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。

输入数据

第一行输入一个正整数n。
以下n行描述该矩阵。矩阵中的数保证是不超过1000的正整数。

输出数据

输出最小伤害值。

样例输入

3
1 3 3
2 2 2
3 1 2

样例输出

8

数据规模

n<=1000