Ryukzak masalasi (0-1)

Shart

Birinchi qatorda buyumlar soni n va ryukzak sigʻimi W berilgan. Keyingi n ta qatorning har birida buyumning ogʻirligi w va qiymati v berilgan. Umumiy ogʻirligi W dan oshmaydigan buyumlar toʻplamining eng katta umumiy qiymatini chiqaring. Har bir buyumni koʻpi bilan bir marta olish mumkin.

Misollar

3 8
3 30
4 50
5 60

90

1 1
2 100

0

Cheklovlar

• 1 ≤ n ≤ 100
• 1 ≤ W ≤ 10^4
• 1 ≤ w ≤ 10^4
• 1 ≤ v ≤ 10^9