Masala #SVMOFBNE5N

Xotira 32 MB Vaqt 1000 ms

Ajoyib sumka

Sizda N ta taqinchoq bor. Har bir taqinchoqning go'zalligi \(Vᵢ\) va og'irligi \(Wᵢ\) berilgan \((1 ≤ i ≤ N)\). Siz ko'proq taqinchoqni tanlab, sumkaga joylashtirishni rejalashtirganiz. Sumkaning og'irlik chegarasi M ga teng. Ya'ni, sumkadagi taqinchoqlarning og'irligi umumiy hisobda M dan oshmasligi kerak.

Sumkaning "kengligi" (G) quyidagicha hisoblanadi:

G = (sumka joylashtirilgan taqinchoqlarning go'zalligining eng kichik qiymati) × (sumkaga joylashtirilgan taqinchoqlarning go'zalligining umumiy summasi).

Agar sumkaga hech qanday taqinchoq joylashtirib bo'lmasa, uning kengligi 0 ga teng bo'ladi.

Sizdan talab qilinadigan narsa – sumkaga taqinchoqlarni tanlab, ularning og'irliklari jami M dan oshmasligi sharti bilan, kenglik (G) ning maksimal qiymatini topish.

Kiruvchi ma'lumotlar:

Birinchi satrda ikkita butun son N va M beriladi:

N – taqinchoqlar soni \((1 ≤ N ≤ 2*10^4)\).
M – sumkaning maksimal og'irligi (\((1 ≤ M ≤ 10^5)\).

Keyingi N satrda har bir taqinchoqning go'zalligi va og'irligi beriladi:

Vᵢ – taqinchoqning go'zalligi \((1 ≤ Vᵢ ≤ 10⁶)\).
Wᵢ – taqinchoqning og'irligi \((1 ≤ Wᵢ ≤ 10^5)\).

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar

#	input.txt	output.txt
1	5 25 11 11 13 3 2 7 1 3 9 7	297
2	5 1 100 1000 100 1000 100 1000 100 1000 100 1000	0

Izoh:

1-testda. 1, 2 va 5 taqinchoqlar tanlansa
11 11
13 3
9 7
lar olinadi. Taqinchoqlarning go'zalligini eng kichik qiymati 9 va umumiy yig'indisi 11+13+9=33 ga teng. Demak 9*33=297 ekan.