羊羊们在玩一个新型的跳格子游戏。它的规则十分简单：在一个N*N的方阵中，羊羊以左上角的格子为起点，羊羊可以从一个各自走到它的右边和下边的格子里。每个格子里都有一个数字，当羊羊们走到相应格子时，就要背上相应数字所示的青草捆数。喜羊羊也参加了这个游戏，他想在背负最少的青草的情况下走到方阵的最右下角。

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

输出背负的最少青草捆数。

3
1 3 3
2 2 2
3 1 2

8

JSOI2012春季函授B层次考试题