题目描述

小L想和你玩一个游戏，在一个n * m的棋盘上，每一个格子里都有一个数字，游戏规则为从左上角行进到右下角，并且每一步只能向右或向下，求一条路径使得数字相加和最小，求最优方案。

输入格式

第一行两个整数 n, m
接下来n行，每行m个数字表示棋盘

输出格式

输出数字相加和最小

样例

####样例输入

10 10
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 1 0
8 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 5

####样例输出

14

数据范围与提示

10 <= n, m <= 10^3
0 <= 棋盘上的数字 <= 10^3