题目内容

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

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

也就是说，从位置 $(i,j)$ 出发，只能移动到位置 $(i+1,j)$ 或位置 $(i,j+1)$。

输入描述

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

接下来输入 $m$ 行，每行包含 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示 $grid_{i,j}$。

相邻整数之间用空格分隔。

约束

$1 \le m,n \le 200$

$0 \le grid_{i,j} \le 200$

输出描述

输出一个整数，表示从网格左上角移动到右下角的所有合法路径中，路径上数字总和的最小值。

样例1

输入

3 3
1 3 1
1 5 1
4 2 1

输出

7

说明

可以选择路径

$1 \rightarrow 3 \rightarrow 1 \rightarrow 1 \rightarrow 1$

该路径上数字的总和为

$1+3+1+1+1=7$

并且不存在路径和更小的合法路径，因此答案为 $7$。

样例2

输入

2 3
1 2 3
4 5 6

输出

12

说明

可以选择路径

$1 \rightarrow 2 \rightarrow 3 \rightarrow 6$

路径上数字的总和为

$1+2+3+6=12$

因此最小路径和为 $12$。