Masala #0594

Xotira 25 MB Vaqt 1000 ms
14
Muallif: Shahzod

Sumka yoki knapsack

Sizga \(n\) va \(c\) summa beriladi. \(n\) ta elementdan iborat \(v\), \(w\) to'plam beriladi. \(i\) uchun \((0 \le i \le n-1)\) \(v[i]\) - qiymat , \(w[i]\) - og'irlik. Sizning vazifangiz maksimal qiymat tanlashingiz kerak bo'ladiki, ularga mos og'irliklar yig'indisi summadan oshmasin.


Kiruvchi ma'lumotlar:

Birinchi qatorda \(n(1 \le n \le 10^3)\) va \(c(0 \le c \le 2*10^6)\) beriladi.
Ikkinchi qatorda \(n\) ta son \(v_0 , v_1, \dots, v_{n-1}\) \((0 \le v_i \le 50)\).
Uchinchi qatorda \(n\) ta son \(w_0, w_1, \dots , w_{n-1}\) \((0 \le w_i \le 50)\).


Chiquvchi ma'lumotlar:

Chiqishda bir qatorda siz tanlashingiz mumkin bo'lgan maksimal qiymat.


Misollar
# input.txt output.txt
1
4 20
10 15 6 4
10 5 10 10
25
Izoh:

Birinchi test uchun biz tanlashimiz mumkin maximal qiymat 25ga teng.
(10+15) ularga mos og'irliklar yig'indis (10+5) u 20 dan katta emas.