题目描述

在一个$m\times n(m> 1,n\le 200)$的二维网格中，我们的无人机从左上角出发去到右下角。

无人机初始电量是一个正整数，如果电量降低到$0$或以下，那么会立即炸机坠毁。

路上经过的所有网格有不同的物理特性，导致无人机经过时消耗的电量不一样（负整数代表消耗的电量值）；

有些网格如此奇妙，对于无人机来说如同瞬间通过不消耗电量（网格数值为$0$）；

还有一些网格无人机经过会增加电量（正整数代表增加的电量）；为了尽快到达右下角，无人机每次只向右或向下移动一步。

请编程计算并返回能够确保无人机到达右下角的最低初始电量。

输入描述

第一行输入两个整数$n,m(1\le n,m\le 200)$，分别表示二维网络的行数和列数。

接下来$n$行，每行输入$m$个整数$a_1,a_2,...a_m(-10^3\le a_i\le 10^3)$，表示每个网格所消耗的电量值。

输出描述

输出一个整数，表示无人机所需要的初始最低电量值。

样例

输入

3 3
-2 -3 3
-5 -10 1
10 30 -5

输出

7

样例解释

$(0,0)\to (1,0)\to (2,0)\to (2,1)\to (2,2)$，最少仅需要$7$电量值。