测试数据来自 system/2796

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在 \(n\) 行 \(m\) 列的棋盘上，棋盘左上角格子的下标是 (1,1)，右上角的下表是 \((n,m)\)，每一个格子有一个整数，表示该格子的分数。现在小H从 \((1,1)\) 走到 \((n,m)\)，每一次只能向下、向左或向右走到相邻的格子中，并取走经过格子的分数，取走后该格子分数变为 0。
　　请你计算小H能得到的最小得分。

【输入格式】

　　第 1 行为\(n,m\)。接下来的 \(n\) 行，每行 \(m\) 个非负整数 \(x（0≤x≤1000）\)，表示格子的分数。

【输出格式】

　　输出小H的最小得分。

【输入输出样例】

　Input

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

　Output

22

【数据限制】

　　对于 \(100\%\) 的数据满足，\(2≤n,m≤1000\)。

【来源】

　　Mr.he