No testdata at current.

题目描述

在一个 $m \times n$ 的二维网格中，我们的无人机从左上角出发飞到右下角。无人机初始电量是一个正整数，如果电量降低到0或以下，那么会立即炸机坠毁。路径经过的所有网格有不同的物理特性，导致无人机经过时消耗的电量不一样（负整数代表消耗的电量）；有些网格如此奇妙，对无人机来说如果瞬间通过不消耗电量（网格数值为0）；还有一些网格无人机经过会增加电量（正整数代表增加的电量）。

为了尽可能安全到达右下角，无人机每次只能向右或向下移动一步。请编程计算并返回能够确保无人机到达右下角的最低初始电量。

输入描述

输入为整数的二维数组。

输出描述

输出为正整数。

示例输入输出

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

7

提示

• $m == \text{grid.length}$
• $n == \text{grid}[i].\text{length}$
• $m \leq 1, n \leq 200$
• $-1000 \leq \text{grid}[i][j] \leq 1000$