题目描述

小 D 来到了群山面前，群山可以用 $n$ 行 $m$ 列的网格表示（以下用 $(i,j)$ 表示第 $i$ 行第 $j$ 列，小 D 在 $(1,1)$，他想到达 $(n,m)$。

若小 D 在 $(i,j)$，他可以花费 $w_{i,j}$ 的法力值到达 $(i+1,j)$。也可以花费 $w_{i,j}$ 的法力值到达 $\forall(i,k) (k\gt j)$。

在 $(i,j)$ 有一个法力值为 $h_{i,j}$ 的宝石，和增幅值为 $a_{i,j}$ 的法阵，在小 D 由 $(i,j)$ 到达 $(i,k)$ 时，可以在第 $i$ 行的第 $j$列到第 $k-1$ 列的宝石中选一个，到达 $(i,k)$ 后使用。假设选择的宝石法力值为 $H$，则小 D 可以增加 $H\times a_{i,k}$ 的法力值。

小 D 初始的法力值为 $F$，由于小 D 可以短暂透支，他并不要求过程中法力值为非负数，但到达 $(n,m)$ 后法力值要为非负数。

如果能够完成，输出小 D 到达 $(n,m)$ 后的最大法力值，否则输出 -1。

输入格式

本题输入量较大，请使用较快的读入方式。

第一行读入 3 个数，表示 $n,m,F$ 。

接下来读入一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列表示 $w_{i,j}$。

接下来读入一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列表示 $h_{i,j}$。

接下来读入一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列表示 $a_{i,j}$。

输出格式

输出一行 1 个整数，如果能够完成，输出小 D 到达 $(n,m)$ 后的最大法力值，否则输出 -1。

数据范围

对于10%的数据：$n,m\le 4$。 对于20%的数据：$n,m\le 30$。 对于40%的数据：$n\le 100$，$m\le 500$。 另有20%的数据：$\max{a_{i,j}}=1$。 另有20%的数据：$\max{a_{i,j}}\le 10$。 对于100%的数据：$n\le 100$，$m\le 20000$，$1\le F,a_{i,j}\le m$，$1\le h_{i,j}\le 10^5$，$1\le w_{i,j}\le 2\times 10^9$。 $\max{a_{i,j}}\le m$，对于 $\forall 1\le i \le n,1\le j \lt n ,a_{i,j} \ge a_{i,j+1}$。

输入样例 1

3 3 4
2 1 2 
2 1 2 
3 3 2 
2 3 1 
1 1 1 
2 3 1 
3 1 1 
3 1 1 
3 1 1

输出样例 1

2

样例解释

以下是一种可行的方法：

$(1,1)->(1,2)$，$F=4-2+2\times 1=4$。

$(1,2)->(1,3)$，$F=4-1+3\times 1=6$。

$(1,3)->(2,3)$，$F=6-2=4$。

$(2,3)->(3,3)$，$F=4-2=2$。