Masala #0594

Xotira 25 MB Vaqt 1000 ms Qiyinchiligi 45 %
3.0 (Baholar 8)
14
Muallif: Shahzod

  

Sumka yoki knapsack

Sizga nn va cc summa beriladi. nn ta elementdan iborat vv, ww to'plam beriladi. ii uchun (0in1)(0 \le i \le n-1) v[i]v[i] - qiymat , w[i]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(1n103)n(1 \le n \le 10^3) va c(0c2106)c(0 \le c \le 2*10^6) beriladi.
Ikkinchi qatorda nn ta son v0 , v1,,vn1v_0 , v_1, \dots, v_{n-1} (0vi50)(0 \le v_i \le 50).
Uchinchi qatorda nn ta son w0,w1,,wn1w_0, w_1, \dots , w_{n-1} (0wi50)(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.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin