路程时间

题目描述

有 $n \times m$ 大小的网格图，每个格子里有一个整数 $t$，表示经过这个格子所需的时间，现在从网格的左上角出发，到达右下角，行进过程只能向右或向下，找到一条用时最短的路径，把需要的时间输出。（起点和终点的时间也要算在总时间里）

输入格式

第一行两个整数 $n$ 和 $m$，表示网格图的大小。

第二行到第 $n+1$ 行，每行 $m$ 个整数 $t$，表示经过格子所需要的时间。

输出格式

一个整数，表示左上角到右下角的最少时间。

样例输入 #1

3 4
1 0 2 3
3 2 2 1
0 1 0 1

样例输出 #1

5

数据范围

$1 \le n, m \le 30$，$0 \le t \le 3$

知识点与难度

本题涉及的知识点从属于 GESP六级（动态规划、网格路径DP），难度等级：⭐⭐⭐。

测试点分布