- Time limit: 1.00 s
- Memory limit: 128 MB
Olet menossa maailmanpyörään n lapsen kanssa, ja tehtäväsi on etsiä jokaiselle lapselle istumapaikka koreista.
Yhdessä korissa voi istua yksi tai kaksi lasta. Lisäksi korin yhteispaino saa olla korkeintaan x. Tiedät jokaisen lapsen painon.
Kuinka monta koria tarvitaan vähintään, jotta kaikki lapset pääsevät maailmanpyörään?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja x: lasten määrä ja korkein sallittu paino.
Seuraavalla rivillä on n kokonaislukua p_1,p_2,\ldots,p_n: kunkin lapsen paino.
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: pienin tarvittava korien määrä.
Rajat
- 1 \le n \le 10^5
- 1 \le x \le 10^9
- 1 \le p_i \le x
Esimerkki
Syöte:
4 10 7 2 3 9
Tuloste:
3