問題文

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

制約

  • 1N,K161 \leq N,K \leq 16
  • 1W1091 \leq W \leq 10^9
  • 1Ai1091 \leq A_i \leq 10^9

入力

入力はすべて整数である。
NN KK WW
A1A_1 A2A_2 ...... ANA_N

出力

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

サンプル

入力1
4 2 100
40 45 50 55
出力2
2

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


入力2
3 1 1
1000000000 1000000000 1000000000
出力2
-1

入力3
6 3 20
2 2 2 3 15 16
出力3
2

入力4
15 5 100
15 15 20 35 35 35 35 35 55 55 55 65 70 85 90
出力4
8

Submit


Go (1.21)