Турист собирается в поход и выбирает, какие вещи положить в рюкзак. Рюкзак выдерживает суммарную массу не более W.

Есть n предметов. Для каждого предмета известны его масса w_i и полезность v_i. Каждый предмет можно взять не более одного раза.

Требуется выбрать набор предметов с суммарной массой не больше W так, чтобы суммарная полезность была максимальной.

Входные данные

В первой строке даны два целых числа n и W — количество предметов и вместимость рюкзака.

В следующих n строках содержится по два целых числа w_i и v_i — масса и полезность i-го предмета.

Выходные данные

Выведите одно целое число — максимальную суммарную полезность предметов, которые можно положить в рюкзак.

Ограничения

• 1 <= n <= 1000
• 1 <= W <= 10^5
• 1 <= w_i <= W
• 1 <= v_i <= 10^9

Примеры

Пример 1

Входные данные

4 7
1 1
3 4
4 5
5 7

Выходные данные

9

Пример 2

Входные данные

5 10
10 100
9 99
6 60
4 41
5 50

Выходные данные

101