题目描述

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

输入格式

输入文件第一行为两个整数 $n,m(1\leq n,m\leq 100)$，接下来 $n$ 行，每行 $m$ 个数字，每个数字不超过1000的正整数，用空格隔开，表示这个网络grid。

输出格式

表示路径上的数字总和的最小值。

样例 #1

样例输入 #1

3 3
1 3 1
1 5 1
4 2 1

样例输出 #1

7

样例 #2

样例输入 #2

2 3
1 2 3
4 5 6

样例输出 #2

12