Рюкзак 0/1: максимальная ценность

Есть n предметов, у предмета i вес wᵢ и ценность vᵢ. Каждый предмет можно взять не больше одного раза. Выберите набор с суммарным весом не больше W и максимальной суммарной ценностью.

Ввод: в первой строке n и W (1 ≤ n ≤ 100, 0 ≤ W ≤ 5·10⁴), далее n строк w v (1 ≤ w ≤ 5·10⁴, 0 ≤ v ≤ 10⁹).

Вывод: максимальная суммарная ценность (может не поместиться в 32 бита).

Пример 1

Ввод:

4 5
1 1
3 4
4 5
2 3

Вывод:

7

Пример 2

Ввод:

1 0
1 100

Вывод:

0