問題文

$N$人が1階におり、1台のエレベーターを使って二階まで上がります。
$i (1 \leq i \leq N)$人目の人の体重は$A_i kg$です。エレベーターに乗る順番に制限はありません。
エレベーターに一度に乗れる人数の上限は$K$人で、総重量の上限は$W kg$です。
$N$人全員を二階に運ぶとき、エレベーターの往復回数の最小値を求めてください。
全員を二階に運ぶことができない場合はそれを報告してください。

制約

• $1 \leq N,K \leq 16$
• $1 \leq W \leq 10^9$
• $1 \leq A_i \leq 10^9$

入力

入力はすべて整数である。
$N$ $K$ $W$
$A_1$ $A_2$ $...$ $A_N$

出力

全員を二階に移動させるために必要な往復回数の最小値を出力してください。
全員を二階に運ぶことが出来ないときは$-1$を出力してください。

サンプル

4 2 100
40 45 50 55

2

1回目の往復で1人目、4人目を乗せ、2回目の往復で2人目、3人目を乗せることで、
2回の往復で4人を2階を移動させることができます。
どちらも2人以下、総重量100kg以下という条件を満たしています。

3 1 1
1000000000 1000000000 1000000000

-1

6 3 20
2 2 2 3 15 16

2

15 5 100
15 15 20 35 35 35 35 35 55 55 55 65 70 85 90

8