最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

输入格式

第一行输入两个整数 m 和 n，表示网格的行数和列数。

接下来输入 m 行，每行 n 个非负整数，表示网格中的元素。

输出格式

输出一个整数，表示从左上角到右下角的最小路径和。

数据范围

1 <= m, n <= 200

0 <= grid[i][j] <= 200

样例 1

输入

3 3
1 3 1
1 5 1
4 2 1

输出

7

样例 2

输入

2 3
1 2 3
4 5 6

输出

12