暂无测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

\(\text{Sprephie}\)给聪明的\(\text{Scarral}\)出了一道题：一个 \(n\) 行 \(m\) 列的网格，每个位置上有一个数字，数字可正可负。小明一开始可以在第 \(n\) 行选择任意一个网格，然后按照如下规则来进行游戏。

1. 我们把小明第一次进入第 \(i\) 行的位置记录下来，假设是 \((i,j)\)。当小明在位置 \((i,j)\) 时，他只能向左走，或者向上走；否则他可以向左走、向右走，或者向上走。
2. 当小明已经走到第 \(1\) 行时，他仍然可以按照规则一执行，但如果他继续向上走，那么游戏结束。

当游戏结束时，小明经过的格子上的数字总和就是小明的分数，那么请问小明得到的最小分数应该是多少？

---

Input

输入第 \(1\) 行两个数 \(n\) 和 \(m\)，表示一个 \(n\) 行 \(m\) 列的矩阵。
接下来是一个 \(n\) 行 \(m\) 列的矩阵。

---

Output

输出 \(1\) 行 \(1\)个整数，表示得分的最小值。

---

Sample

Sample input

#1

4 4
-1 2 -3 3
-7 -8 -9 -10
-7 20 -3 15
-8 7 0 -1

#2

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

#3

3 3
-1 -3 2
5 -1 -6
-3 7 -6

Sample output

#1

-32

#2

-2

#3

-17

---

Hint

对于 \(30\%\) 的数据，\(1\le n,m\le 10\)，\(-10\le\) 矩阵中数字 \(\le 10\)；
对于 \(60\%\) 的数据，\(1\le n,m\le 50\)，\(-100\le\) 矩阵中数字 \(\le 100\)；
对于所有的数据，\(1\le n,m\le 10^3\)，\(-3\cdot 10^4\le\) 矩阵中数字 \(\le 3\cdot 10^4\)。