Masala #0594
Sumka yoki knapsack
Sizga va summa beriladi. ta elementdan iborat , to'plam beriladi. uchun - qiymat , - og'irlik. Sizning vazifangiz maksimal qiymat tanlashingiz kerak bo'ladiki, ularga mos og'irliklar yig'indisi summadan oshmasin.
Birinchi qatorda va beriladi.
Ikkinchi qatorda ta son .
Uchinchi qatorda ta son .
Chiqishda bir qatorda siz tanlashingiz mumkin bo'lgan maksimal qiymat.
# | input.txt | output.txt |
---|---|---|
1 |
4 20 10 15 6 4 10 5 10 10 |
25 |
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.