問題文

次回のプログラミングコンテスト「ABC10000」で、岩井星人さんは満足したいと考えています。コンテスト運営であるあなたの仕事は、問題案の中から良いものを採用しつつ、同時に岩井星人さんを満足させてあげることです。

問題案は $N$ 個あり、 $1, 2, ..., N$ の番号が付けられています。
岩井星人さんは問題案 $i$ が採用されたとき、満足度を $A_i$ 得ます。（$A_i$ は負であることもあります）
また、問題案 $i$ は、美しさを $C_i$ 持っています。

美しさの合計が $K$ 以上になるように相異なる $D$ 個の問題案を採用したときに、岩井星人さんが得られる満足度の最大値を出力してください。
ただし、美しさの合計が $K$ 以上とならない場合は No と出力してください。

制約

• $1\leq D\leq N\leq 500$
• $1\leq K\leq 500$
• $-10^9\leq A_i\leq 10^9$
• $0\leq C_i\leq 10^9$
• 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N\quad D\quad K$
$A_1\quad A_2\quad ... \quad A_{N-1} \quad A_N$
$C_1\quad C_2\quad ... \quad C_{N-1} \quad C_N$

出力

条件を満たす最大の満足度を出力せよ。
条件を満たすことが不可能な場合は、No を出力せよ。

サンプル

5 3 20
20 10 -15 30 20
3 8 11 9 6

60

1 1 500
3
10

No

16 8 240
101 -202 300 400 -430 700 -720 820 -830 -890 910 -970 990 1013 -1250 1270
50 20 15 35 25 30 35 40 20 30 10 35 0 20 35 20

4494