D. Qayiqlar

Litsey o‘quvchilari sayohatga chiqishdi va daryodan qayiqlarda o‘tishlari kerak. Jami N nafar o‘quvchi bor, i-o‘quvchining vazni wᵢ kilogramm.

Har bir qayiqqa ko‘pi bilan 2 kishi o‘tiradi, o‘tirganlarning umumiy vazni esa qayiq sig‘imi C dan oshmasligi kerak. Barcha qayiqlar bir xil. Har bir o‘quvchining vazni C dan oshmaydi, ya’ni har kim kamida yolg‘iz o‘zi o‘ta oladi.

Hamma o‘quvchini daryodan o‘tkazish uchun eng kamida nechta qayiq kerak?

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son: N — o‘quvchilar soni va C — qayiq sig‘imi.

Ikkinchi qatorda probel bilan ajratilgan N ta butun son: w₁, w₂, …, wₙ.

Chiqish ma’lumotlari

Bitta butun son — eng kam qayiqlar soni.

Cheklovlar

1 ≤ N ≤ 10^5

1 ≤ wᵢ ≤ C ≤ 10^9

1-misol rasmda ko‘rsatilgan: (80, 20), (70, 30) va (50) — 3 ta qayiq. Kamroq qayiq bilan bo‘lmaydi: 50, 70 va 80 kg li o‘quvchilarning hech qaysi ikkitasi bir qayiqqa sig‘maydi.

2-misolda har bir o‘quvchi qayiqni to‘liq egallaydi.

Diqqat: ikki vaznning yig‘indisi 2 · 10^9 gacha yetadi — C++ va Java da int turi to‘lib ketishi mumkin.