F. Dasturxon

To‘yda dasturxonga N ta taom bir qatorga terilgan. i-taomning to‘yimliligi fᵢ, achchiqligi sᵢ. Ahmad qatordan ketma-ket turgan bir nechta taomni (uzluksiz bo‘lakni) tanlab, ularning hammasidan tatib ko‘radi. To‘yishi uchun tanlangan taomlar to‘yimliliklari yig‘indisi kamida M bo‘lishi kerak.

Ahmad achchiqni yoqtirmaydi. Bo‘lakning achchiqligi — undagi taomlar achchiqligining eng kattasi. Ahmad to‘yadigan bo‘laklar ichidan achchiqligi eng kichigini tanlaydi, bunday bo‘laklar bir nechta bo‘lsa — eng qisqasini (taomlar soni eng kamini).

Tanlangan bo‘lakning achchiqligi va uzunligini toping.

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son N va M.

Keyingi N ta qatorning i-sida ikkita butun son fᵢ va sᵢ — i-taomning to‘yimliligi va achchiqligi (taomlar qatordagi tartibda berilgan).

Chiqish ma’lumotlari

Bitta qatorda ikkita butun son: tanlangan bo‘lakning achchiqligi va undagi taomlar soni.

Cheklovlar

• 1 ≤ N ≤ 2·10⁵
• 1 ≤ fᵢ, sᵢ ≤ 10⁹
• 1 ≤ M ≤ f₁ + f₂ + … + f_N (ya’ni hamma taomni yesa, Ahmad albatta to‘yadi)
• Yig‘indilar 32 bitli songa sig‘maydi: C++ da long long ishlating.

1-misol: 3-, 4- va 5-taomlar: to‘yimlilik 5 + 4 + 3 = 12, achchiqlik max(2, 6, 3) = 6. Achchiqligi 6 dan kichik bo‘lak bilan to‘yib bo‘lmaydi: 7 va 9 achchiqlikdagi taomlarsiz eng uzun bo‘lak — 3-, 4-, 5-taomlar, ulardan boshqasi esa yig‘indisi 12 ga yetmaydi.

2-misol: bitta taom — u to‘yishga yetadi.