龙卷风摧毁停车场

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

阿福给了你一个能量为 $p$ 的龙卷风!他要你拿龙卷风去摧毁停车场(龙卷风:mmp)。

我们可以把停车场看作一个 $n \times m$ 的二维平面,每个位置上都停着一辆车,每辆车都有两个属性 $c_{i}$ 和  $v_{i}$,分别表示龙卷风摧毁这辆车需要消耗的能量,以及摧毁后可以获得的成就值。

初始时你的龙卷风位于 $(1, 1)$ 位置,每次移动只能向右或向下移动一格,且会消耗 $1$ 个单位的能量。当你的龙卷风到达一个新的位置 $(x, y)$ 时,它便开始试图摧毁此位置上的汽车。如果摧毁成功,你就将获得对应的成就值。

当龙卷风的能量值消耗殆尽或无法移动(已在右下角)时则视为龙卷风已 gg。阿福会结算你收获的总成就值并回收龙卷风充能以便给下一个提交本题的人使用。

现在你应该很想知道,自己到底怎么操控龙卷风,才能获得最大的成就值呢?

Input

第一行输入 $3$ 个整数 $n$, $m$, $p$ $(1 \leqslant n, m, p \leqslant 100)$,分别表示停车场的尺寸以及龙卷风的初始能量。

接下来输入 $n$ 行,每行 $m$ 个空格分隔的整数 $c_{i}$ $(2 < c_{i} \leqslant 100)$,表示摧毁此位置上汽车的所要消耗的能量。

接下来再输入 $n$ 行,每行 $m$ 个空格分隔的整数 $v_{i}$ $(1 \leqslant v_{i} \leqslant 100)$,表示摧毁此位置上汽车后能获得的成就值。

Output

输出一个整数,表示能获得的最大总成就值。

Sample Input

2 3 10
1 2 10
5 1 4
10 15 30
50 30 60

Sample Output

90

Hint

Source

【2016级ACM暑假集训 结训赛(数据结构组)】QAQrz & bLue