EOJ-自适应编程学习平台

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

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

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

迷宫的入口在左上角，出口在右下角，由于 ultmaster 方位感惊人，他竟然能保证自己只往右或者往下走。

那么问题来了，从迷宫出去之后，ultmaster 最多能剩多少寿元呢？

<img src="/upload/3281/daffy.22a75f3804fb403340b4a25b3006e9e2.jpg" class="graphics">

第一行三个整数 $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$。

2 2 1
0 2
2 -3

0

2 2 1
0 2
4 -3

2

2 3 1
0 -1 0
0 -3 0

0

2 2 1
0 -2
-2 3

-1

2 2 9
-1 -2
-3 -4

2