問題文


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

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

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

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

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

制約


  • 入力はすべて整数

入力


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

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

出力


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

入力例 1


4 3 14
3 4 5 6
1 6 5 9

出力例 1


5

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

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

入力例 2


4 3 11
3 4 5 6
1 6 5 9

出力例 2


-1

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

Submit


Go (1.14)