题目描述

有一个N*M的矩阵方格，每个方格中都有一个正整数，现从左上角方格出发向右下角方格移动，每次只能向下或向右移动一个方格，请你找出一条最小路径（路径上的正整数之和最小），并输出该路径上的正整数之和。

示例说明

例如N=2，M=3的矩阵如下： | 1 | 3 | 5 | |---|---|---| | 2 | 4 | 6 | 按照移动规则，从左上角到右下角的路径共3条：

1. 1->3->5->6，和为15
2. 1->3->4->6，和为14
3. 1->2->4->6，和为13 其中最小路径和为13，故输出13。

输入描述

第一行输入两个正整数N和M（2≤N≤100，2≤M≤100），N表示矩阵行数，M表示矩阵列数，两个整数之间以空格分隔。 第二行开始输入N行，每行M个正整数（1≤正整数≤200），整数之间以空格分隔。

输出描述

输出一个整数，表示最小路径上的正整数之和。

样例输入

2 3
1 3 5
2 4 6

样例输出

13

参考测试用例

2 3 1 2 3 4 5 6

| ```
3 3
1 3 1
1 5 1
4 2 1
``` | 7 |
| ```
4 8
2 7 3 4 1 5 9 6
9 8 7 6 5 4 3 2
3 4 2 1 7 4 5 3
8 7 2 4 1 2 6 3
``` | 37 |
| ```
6 9
9 8 7 6 5 4 3 2 1
1 3 1 6 5 4 3 2 6
1 6 5 4 3 2 2 6 9
2 4 47 2 4 1 2 6 1
2 5 2 7 2 4 1 2 6
5 8 2 7 3 4 5 9 4
``` | 44 |
| ```
10 15
3 4 1 7 4 5 2 8 7 2 4 23 12 12 34
13 41 11 71 14 15 12 81 17 12 14 23 12 12 34
32 42 21 27 42 5 22 8 27 2 4 23 12 12 34
13 4 1 37 4 35 32 8 7 23 4 13 7 43 53
53 45 22 14 72 44 52 39 29 58 28 78 22 42 18
12 6 3 22 51 2 71 2 4 13 2 56 5 22 8
58 37 46 25 14 73 42 51 30 22 71 34 13 23 62
12 25 21 9 8 77 26 57 4 63 12 71 21 27 62
17 6 52 4 23 2 22 6 9 22 5 2 77 21 24
22 52 12 47 52 64 11 76 5 74 53 24 24 61 29
``` | 247 |