Lunch

問題文

ある学食では、主菜が $N$ 品、副菜が $M$ 品 販売されています。
$i \, (1 \leq i \leq N)$ 番目の主菜の値段は $A_i$ 円、美味しさは $B_i$ です。
また、$j \, (1 \leq j \leq M)$ 番目の副菜の値段は $C_j$ 円、美味しさは $D_j$ です。

処理犬君は、主菜から $1$ 品、副菜から $1$ 品を選んで今日のお昼ご飯にしようと考えていますが、財布には $K$ 円しか入っていません。

合計の値段が $K$ 円を超えないように、主菜と副菜それぞれから $1$ 品ずつ選んだとき、選んだ主菜と副菜の美味しさの合計の最大値を求めてください。

制約

• $1 \leq N, M \leq 1000$
• $2 \leq K \leq 10^9$
• $1 \leq A_i, C_j \leq 10^9$
• $1 \leq B_i, D_j \leq 10^9$
• 入力は全て整数
• 合計の値段が $K$ 円以下となる主菜・副菜の組み合わせが少なくとも 1 つ存在することが保証される。

入力

N M K
A_1 A_2 ... A_N
B_1 B_2 ... B_N
C_1 C_2 ... C_M
D_1 D_2 ... D_M

• $1$ 行目に整数 主菜の数 $N$, 副菜の数 $M$, 残金 $K$ が空白区切りで与えられます。
• $2$ 行目にそれぞれの主菜の値段が空白区切りで与えられます。
• $3$ 行目にそれぞれの主菜の美味しさが空白区切りで与えられます。
• $4$ 行目にそれぞれの副菜の値段が空白区切りで与えられます。
• $5$ 行目にそれぞれの副菜の美味しさが空白区切りで与えられます。

出力

合計の値段が $K$ 円を超えないように、主菜と副菜それぞれから $1$ 品ずつ選んだとき、選んだ主菜と副菜の美味しさの合計の最大値を求めてください。

入力例 1

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

出力例 1

14

$2$ 番目の主菜、 $3$ 番目の副菜を選んだ時、合計の値段は $3$ 円で、美味しさの合計は $14$ です。$K$ 円以内で、主菜・副菜を $1$ 品ずつ選んだとき、美味しさの合計を $14$ より大きくすることはできないので、$14$ を出力します。

入力例 2

1 1 2
1
1
1
1

出力例 2

2