UVA1427 Parade

F 城的统治者帕纳戈拉大人酷爱游行。他总是乘坐专车巡视城市，享受臣民的欢迎。 F 城拥有规整的道路系统——由 $n+1$ 条东西走向的道路和 $m+1$ 条南北走向的道路构成网格状，自然形成了 $(n+1)\times(m+1)$ 个十字路口。游行可以从最南端任意路口开始，在最北端任意路口结束。帕纳戈拉的路线永不往南折返，也不会重复经过同一路口。 臣民们会沿着每条东西道路的两侧迎接他——爱戴者献上热烈欢迎，憎恶者则投掷鸡蛋番茄。我们把东西道路上相邻路口之间的路段称为“爱憎区间”，每条东西道路包含 $m$ 个这样的区间。经过每个爱憎区间时，根据民众态度，帕纳戈拉的愉悦值会增减，因此每个区间都有可正可负的“欢迎值”。作为他的秘书，你必须规划出让帕纳戈拉最开心的路线——即欢迎值总和最大的路径，并自主决定起止位置。 向臣民挥手致意时，帕纳戈拉可能会疲惫需要休息。因此请确保他在同一条东西道路上停留不超过 $k$ 分钟。若通过某个爱憎区间需耗时$p$分钟，则称该区间长度为 $p$。所有区间的长度数据都已提供。

多组测试数据，以包含三个零的行结束。 每组数据包含 $2\times n + 3$ 行： 首行为三个整数 $n, m, k$（$0 < n \le 100$，$0 < m \le 10000$，$0 \le k \le 3000000$） 接下来 $n+1$ 行按从北到南顺序描述各条东西道路，每行 $m$ 个整数表示该道路各爱憎区间的欢迎值（自西向东排列） 最后 $n+1$ 行同样按从北到南顺序描述各条东西道路，每行 $m$ 个整数表示该道路各爱憎区间的长度（分钟数，自西向东排列）

对于每组数据，输出最优路线的欢迎值总和。结果保证在$32$位整数范围内。

下图展示了样例输入的情形，最优路线已用粗线标出。