U23130.偷珠宝

强盗 $A$ 等 $n$ 人来到了一个矩形山洞内部，矩阵的长和宽分别是 $w,h$ 他们想要偷走山洞另一角的珠宝。但是，可恶的构思小灯（一个人名）在山洞的每个格子上都埋有地雷，位置 $(i,j)$ 的地雷有 $a_{i,j}$ 个，即需要 $a_{i,j}$ 个人去踩。而且，构思小灯还施了魔法，所有人都只能向右或向下走。但是，在山东另一角的珠宝也不是他们能随便拿走的。这里有 $m$ 种珠宝，每种珠宝有 $2^{10000000}$ 个，第 $i$ 种珠宝价值是 $\$c_i$，重量是 $v_i\ kg$。已知强盗每人平均能带走的珠宝重量是 $k\ kg$。现在，$A$ 想问问你，他们最多能拿到多少美元？

第一行是 $5$ 个正整数 $n,m,k,w,h$，分别表示强盗的人数、珠宝的种类数、强盗每人平均能带走的珠宝重量以及山洞的长宽。
第 $2$ ~ $w+1$ 行，每行 $h$ 个正整数，其中从第 $2$ 行、第 $1$ 列起的第 $i$ 行第 $j$ 列的数 $a_{i,j}$ 表示在格子 $(i,j)$ 上的地雷数量。
接下来有 $m$ 行，每行 $2$ 个正整数 $c_i,v_i$，表示第 $i$ 种珠宝的价值和重量。当然，$i \in [1,m]$。

只有一个数，如果能拿到珠宝，输出最多能拿到的美元。如果不能拿到，输出 $-1$。

说明提示

强盗从左上角 $(1,1)$ 开始走，珠宝位于右下角 $(w,h)$ 处。保证 $a_{1,1}=0$。

---

样例说明

显然，如下走最合适：

$$(1,1) -> (1,2) -> (2,2) -> (3,2) -> (3,3)$$

需要 $10$ 个强盗牺牲，还剩 $20$ 人。
珠宝可以全部选择价值 $\$8$，重量 $10\ kg$ 的珠宝，能得到 $\$80$。

---

数据范围

对于 $40\%$ 的数据，$1 \leq n,m,k \leq 100$。
对于 $100\%$ 的数据，$1 \leq n,m,k \leq 400$，$1 \leq w,h \leq 3\times 10^3$，$0 \leq a_{i,j} \leq 20$，$1 \leq c_i,v_i \leq 10^9$。