最小初始体力的山洞之旅

题目描述

勘探员背着装备穿行在火山洞穴，洞穴被划成 $n\times m$ 个格子。每迈入一个格子都会改变当前体力值：正数表示补给，负数表示消耗。勘探员从起点 $(1,1)$ 到终点 $(n,m)$ 只能向右或向下移动，并且行进过程中体力值不能降到 $0$ 以下。请你求出他至少需要多少初始体力值才能保证安全到达终点。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示各格子的体力变化。

输出格式

输出一个整数，表示最低初始体力值；若无论初始体力多大都无法到达终点（例如终点被过大消耗包围），输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

7

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 200$，每个格子数值满足 $-1000 \le a_{i,j} \le 1000$。EOF