下降路径最小和

题目描述

在一座悬空的玻璃温室里，花匠要从顶部的一排花台挑选一个起点，沿着向下延伸的花台层层巡视到底部。温室共有 $n$ 行、每行 $m$ 个花台，每往下一层只能走到正下方、左下方或右下方相邻的花台。每个花台都有一个维护成本，请你帮花匠找到一条从第一行任意位置出发到最后一行的路线，使总成本最小。

输入格式

第一行包含两个整数 $n,m$，表示温室的行数和每行花台数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示对应花台的维护成本。

输出格式

输出一个整数，表示可能达到的最小总成本。

输入输出样例 #1

输入 #1

4 4
2 1 3 4
6 5 4 1
1 2 3 4
7 8 1 2

输出 #1

7

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 200$，花台成本满足 $-10^4 \le c_{i,j} \le 10^4$。保证至少存在一条从顶部到底部的路径。EOF