Charxpalak

$n$ ta bola charxpalakka chiqmoqchi, $i$-bolaning vazni $p_i$. Har bir kabinaga bitta yoki ikkita bola o'tiradi, kabinadagi bolalar vaznlari yig'indisi $x$ dan oshmasligi kerak. Barcha bolalar uchun eng kamida nechta kabina kerak?

Birinchi qatorda $n$ va $x$ ($1 \le n \le 2 \cdot 10^5$, $1 \le x \le 2 \cdot 10^9$). Ikkinchi qatorda $n$ ta butun son $p_i$ ($1 \le p_i \le x$).

Bitta son — kabinalarning eng kam soni.

Vaznlarni saralang va ikki ko'rsatkich qo'ying: eng yengil ($l$) va eng og'ir ($r$) bola. Eng og'ir bola baribir biror kabinaga o'tiradi; agar unga eng yengil bola sig'sa, ularni birga o'tqazing ($l$ ni ham suring), aks holda og'ir bola yolg'iz ketadi. Har qadamda $r$ kamayadi, demak $O(n)$.

$p_l + p_r$ $4 \cdot 10^9$ gacha yetadi va 32 bitli int ga sig'maydi.

Manba: CSES, 1090-masala.