1019: ultmaster的逃离

中华大地上，人人都知道有一个叫做 ultmaster 的 dalao。这倒不是因为他在器乐领域、作曲领域、算法竞赛领域与机器学习领域都已经臻至化境，而是因为他实在是太萌了。

他总是喜欢到世界各处探险，可是呢遗憾的是总有那么些地方不仅难走还危机丛生。

这一次，他来到了一个 m 行 n 列的迷宫，迷宫中有的格子里有可以增加寿元的草药，有的空空如也，有的却有减少寿元的毒气。增加寿元的草药当然要吃，减少寿元的毒气却也不得不吸。在进迷宫之前，ultmaster 拥有的寿元为 h。要保证不能有任何一个时刻寿元值小于 0 （不包括 0），不然 ultmaster 就会死在路上。

迷宫的入口在左上角，出口在右下角，由于 ultmaster 方位感惊人，他竟然能保证自己只往右或者往下走。
那么问题来了，从迷宫出去之后，ultmaster 最多能剩多少寿元呢？

输入文件名为 escape.in。

第一行三个整数m,n,h

接下来的m行，每行n个整数，分别代表ultmaster在相应格子中将要改变的寿元（即这个整数大于0为上述的格子内有草药的情况，等于0为上述的格子内空空如也的情况，小于0为上述的格子内有毒气的情况），每个整数绝对值不超过100，整数的绝对值表示对寿元产生的影响（即增加或减少的数目）。

输出文件名为 escape.out。

输出一行一个整数表示答案。

如果ultmaster一定会死在路上，输出 −1。

2 2 1
0 2
2 -3

0