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