2017 历史的进程 Week 5：「一场」测验赛
C. 找不到路哒 ultmaster
单点时限: 3.0 sec
内存限制: 256 MB
中华大地上，人人都知道有一个叫做 ultmaster 的 dalao。这倒不是因为他在器乐领域、作曲领域、算法竞赛领域与机器学习领域都已经臻至化境，而是因为他实在是太萌了。
他总是喜欢到世界各处探险，可是呢遗憾的是总有那么些地方不仅难走还危机丛生。
这一次，他来到了一个 $m$ 行 $n$ 列的迷宫，迷宫中有的格子里有可以增加寿元的草药，有的空空如也，有的却有减少寿元的毒气（？？？）。增加寿元的草药当然要吃，减少寿元的毒气却也不得不吸。在进迷宫之前，ultmaster 拥有的寿元为 $h$。要保证不能有任何一个时刻寿元值小于 $0$ （不包括 $0$），不然 ultmaster 就会死在路上。
迷宫的入口在左上角，出口在右下角，由于 ultmaster 方位感惊人，他竟然能保证自己只往右或者往下走。
那么问题来了，从迷宫出去之后，ultmaster 最多能剩多少寿元呢？
输入格式
第一行三个整数 $m, n, h$ $(1 \leq m,n \leq 1~000, 1 \leq h \leq 10^5)$。
接下来的 $m$ 行，每行 $n$ 个整数，分别代表 ultmaster 在相应格子中将要改变的寿元（即这个整数大于 $0$ 为上述的格子内有草药的情况，等于 $0$ 为上述的格子内空空如也的情况，小于 $0$ 为上述的格子内有毒气的情况），每个整数绝对值不超过 $100$，整数的绝对值表示对寿元产生的影响（即增加或减少的数目）。
输出格式
输出一行一个整数表示答案。
如果 ultmaster 一定会死在路上，输出 $-1$。
样例
Input
2 2 1 0 2 2 -3
Output
0
Input
2 2 1 0 2 4 -3
Output
2
Input
2 3 1 0 -1 0 0 -3 0
Output
0
Input
2 2 1 0 -2 -2 3
Output
-1
Input
2 2 9 -1 -2 -3 -4
Output
2
通知
比赛状态发生变化，点 OK 刷新。
通知