問題文

$N$ 個の宝石があります。 これらの宝石の重さは $W_1, W_2, \ldots, W_N$ であり、綺麗さは $B_1, B_2, \ldots, B_N$ です。

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

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

• 選んだ宝石の綺麗さを、並べた順番に $C_1, C_2, \ldots, C_K$ とする。
• ネックレスの不均一さは、$\Sigma_{i=1}^{K-1} |C_i - C_{i+1}|$

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

制約

• $1 \leq K \leq N \leq 17$
• $1 \leq M \leq 10^{15}$
• $1 \leq W_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• 入力はすべて整数

入力

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

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

出力

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

入力例 1

4 3 14
3 4 5 6
1 6 5 9

出力例 1

5

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

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

入力例 2

4 3 11
3 4 5 6
1 6 5 9

出力例 2

-1

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