Aquamarine

個の宝石があります。 これらの宝石の重さは であり、綺麗さは です。

これらの宝石からちょうど 個選んで、自由に並べてネックレスを作ります。 ただし、選ぶ宝石の重さを総和したものが 以下である必要があります。

このネックレスの不均一さは以下のように決まります。

• 選んだ宝石の綺麗さを、並べた順番に とする。
• ネックレスの不均一さは、

上手く宝石を選ぶことで達成できる、不均一さの最小値を求めてください。 ただし、重さの総和が 以下となるようにちょうど 個選ぶことが出来ない場合は、それを報告してください。

• 入力はすべて整数

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

N K M
W_1 W_2 ... W_N
B_1 B_2 ... B_N

解を一行に出力してください。 重さの総和が 以下となるようにちょうど 個選ぶことが出来ない場合は、-1 と出力してください。

4 3 14
3 4 5 6
1 6 5 9

5

重さの合計が 以下になるように、ちょうど つの宝石を選ぶ必要があります。

そのような選び方は 通りありますが、 そのうちの価値が となるような選び方について、 と並べる場合が最も不均一さが小さくなる場合です。

4 3 11
3 4 5 6
1 6 5 9

-1

重さの合計が 以下になるように、ちょうど つの宝石を選ぶ必要があります。 そのような選び方は存在しないので、-1 と出力してください。