小珅要把 $n$ 件货物从 A 地运到 B 地。第 $i$ 件货物的重量为 $w_i$，卖出后可获得 $v_i$ 个金币。普通货船最多装载总重量 $S_0$ 的货物。

小珅还可以从 $m$ 位魔法师中至多雇佣一位。雇佣第 $j$ 位魔法师需要支付 $C_j$ 个金币，并把货船容量变为 $S_j$。小珅也可以不雇佣任何魔法师。

每件货物最多装一次。请计算“卖出货物所得金币减去雇佣费用”的最大值。

输入格式

第一行三个整数 $n,m,S_0$。

第二行 $n$ 个整数 $w_1,w_2,\ldots,w_n$。

第三行 $n$ 个整数 $v_1,v_2,\ldots,v_n$。

第四行 $m$ 个整数 $S_1,S_2,\ldots,S_m$。

第五行 $m$ 个整数 $C_1,C_2,\ldots,C_m$。

输出格式

输出最多可以获得的金币数量。

5 3 2
1 6 6 4 4
9 3 3 7 9
18 7 16
9 8 3

25

样例说明

雇佣第 $3$ 位魔法师花费 $3$ 个金币，装入第 $1,2,4,5$ 件货物可获得 $28$ 个金币，最终收益为 $28-3=25$。

数据范围

$1\le n,m\le100$，$1\le S_0,S_j\le10000$，$1\le w_i,v_i\le1000$，$1\le C_j\le10000$。

1 1 1
22
109
12
93

0

2 2 8
23 31
24 1
212 179
231 192

0