Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2015 - командный тур


2. Монохромия

Автор задачи: Хаустов Павел
Источник: Региональная олимпиада по программированию 2015, командный тур
Ограничение по времени: 1 с.
Ограничение по памяти: 128 МБ

Имеется n предметов. Каждый предмет имеет свои вес и стоимость. Необходимо выбрать такое подмножество предметов, чтобы его суммарный вес не превосходил m, а его суммарная стоимость была максимально возможной.

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

В первой строке входных данных находятся два целых числа n и m (1 ≤ n ≤ 5·104, 1 ≤ m ≤ 5·104). В каждой из последующих n строк записана пара целых чисел wi и pi — вес i-го предмета и его стоимость соответственно (1 ≤ wi ≤ 20, 1 ≤ pi ≤ 20).

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

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

Примеры
Стандартный вводСтандартный вывод
8 14
2 2
3 4
5 6
2 2
7 8
3 4
2 2
7 8
16