AL09-5. Ryukzak

Sayohatchining ryukzagiga W kg sig‘adi. n ta buyum bor, har birining vazni wᵢ va qiymati vᵢ. Har buyumni ko‘pi bilan bir marta olish mumkin. Qiymatlar yig‘indisi eng katta bo‘lsin.

dp[c] — c kg sig‘imda erishiladigan eng katta qiymat. Buyumlarni bittalab qo‘shing va c ni kattadan kichikka yuring — aks holda bitta buyum ikki marta olinib qoladi.

Kirish ma’lumotlari

Birinchi qatorda n va W, keyingi n qatorda wᵢ vᵢ.

Chiqish ma’lumotlari

Eng katta qiymat.

Cheklovlar

1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁴, 1 ≤ wᵢ ≤ W, 1 ≤ vᵢ ≤ 10⁶