問題文

ぴなさんは、容量 $W$ のナップサックを持って商店街に来ています。商店街には $N$ 個の商品が売られており、また、ぴなさんは $M$ 種類の魔法が使えます。
ナップサックには、入っている商品などに応じて重さ $w$ と価値 $v$ が定まります。初め $w=0,v=0$ です。
ぴなさんは、操作の前後で $0 \leq w \leq W$ を満たす限り、以下の $N+M$ 通りの操作を好きな順で行うことができます。(各操作は $1$ 回までしか行うことができません。行わない操作があっても構いません。)
価値 $v$ を最大化してください。

• $1 \leq i \leq N$ なる $i$ を選び、 $i$ 番目の商品を購入する。
  $w$ の値が $A_i$、 $v$ の値が $B_i$ 増える。
• $1 \leq i \leq M$ なる $i$ を選び、 $i$ 番目の魔法を使用する。
  $w$ の値が $C_i$、 $v$ の値が $D_i$ 減る。

入力

$N\ M\ W$
$A_1\ \cdots\ A_N$
$B_1\ \cdots\ B_N$
$C_1\ \cdots\ C_M$
$D_1\ \cdots\ D_M$

• $1 \leq N \leq 7$
• $1 \leq M \leq 7$
• $1 \leq W \leq 500$
• $1 \leq A_i \leq W$
• $1 \leq B_i \leq 10^8$
• $1 \leq C_i \leq W$
• $1 \leq D_i \leq 10^8$
• 入力は全て整数

出力

価値 $v$ として有り得る値の最大値を出力してください。 最後に改行してください。

サンプル

2 2 30
5 20
10 15
10 5
20 5

25

2 2 30
15 20
10 15
10 5 
20 5

20