Masala #VX3YF3ZUHW

Xotira 32 MB Vaqt 1000 ms
14

Konfetlar

Azimjon konfetlarni juda yaxshi ko'radi. Bu safar u Robolandiya konfetlaridan yeb ko'rishga qaror qildi. U shu mamlakatga kelib qarasaki, konfetlar o'zining mamlakatidagidan ko'ra ancha shirinroq ekan. Endi u iloji boricha ko'proq sondagi konfetlarni o'zining mamlakatiga olib ketmoqchi bo'ldi va Roboshop do'koniga tashrif buyurdi. Bu do'konda jami \(N\) xil turdagi konfetlar bo'lib, har bir turdagi konfetlar yo'lakdagi rastalarda bir qatorda joylashtirilgan. Ammo, bu dokonni o'ziga yarasha qonunlari bor: hech qaysi yonma-yon turgan ikki hil turdagi rastadan konfet sotib olish mumkin emas va qaysidur turdagi konfetni olmoqchi bo'lsa, bu turda mavjud barcha konfetlarni sotib olishi shart! \(i-\)rastada  \(a[i]\) ta quti mavjud va har bir quti ichida \(b[i]\) ta konfet bor(bunda barcha \(a[i]\) ta qutidagi konfetlarni olishi kerak). Bu rastadagi barcha konfetlarni olish uchun \(c[i]\) so'm pul to'lash lozim.  Azimjon dokonga kirishidan oldin qarasa unda \(B\) so'm pul bor ekan. Endi u uyiga necha dona konfet olib keta olishini aniqlamoqchi. Siz unga yordam bering.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita natural son \(N,B(1 \leq N, B \leq 1000)\) sonlari kiritiladi.
Ikkinchi qatorda \(a(1 \leq a[i] \leq 10^5)\) massivi elementlari kiritiladi.
Uchinchi qatorda \(b(1 \leq b[i] \leq 10^5)\) massivi elementlari kiritiladi.
To'rtinchi qatorda esa \(c(1 \leq c[i] \leq 1000)\) massivi elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Azimjonda bor puldan ko'p pul sarflamay maksimal necha dona konfet sotib olish mumkinligini chop eting.


Misollar
# input.txt output.txt
1
5 10
3 2 5 10 7
1 2 3 1 4
2 1 4 2 3
46
Izoh:

Python dasturlash tilida ishlaydiganlar uchun python3.12 dan foydalanishni maslahat beramiz