DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選

C - 収納


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 300

問題文

N 本の棒があり、 i(1≦i≦N) 本目の棒の長さは L_i です。

これらを長さ C のケースに収納していきます。

ケースには 1 本か 2 本の棒を収納できますが、棒を収納できる条件は

  • 1 本の棒を収納するには、棒の長さが a のとき、 a≦C
  • 2 本の棒を収納するには、棒の長さが a,b のとき、 a+b+1≦C

です。

全ての棒を収納するのに、ケースは最小でいくつ必要か答えてください。

制約

  • 1≦N≦100000
  • 1≦C≦10^9
  • 1≦L_i≦C
  • 入力は整数からなる

入力

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

N C
L_1
:
L_N

出力

ケースが最小で x 個必要な時、 x を出力せよ。


入力例 1

4 10
2
8
4
5

出力例 1

3

3 番目の棒と 4 番目の棒を同じケースに収納し、 1 番目の棒と 2 番目の棒をそれぞれ別のケースに収納すると、 3 個のケースに収納することができます。


入力例 2

3 10
1
1
1

出力例 2

2

1 つのケースには 2 本までの棒しか収納できないことに注意して下さい。


入力例 3

9 30
22
5
2
18
6
21
29
11
18

出力例 3

5

Submit提出する