Educational Codeforces Round 21 |
---|
Закончено |
После нескольких реформ в Берляндию стали гораздо чаще приезжать туристы, и многие жители Берляндии, смекнув, что в туристическом бизнесе можно очень неплохо заработать, решили сменить место работы. Петя, например, бросил работу в IT-фирме и стал продавать сувениры на рынке.
Как и всегда, этим утром Петя собрался на рынок. У Пети дома стоит n различных сувениров; i-й сувенир характеризуется своим весом wi и стоимостью ci. По предыдущим дням Петя понял, что, скорее всего, ему не удастся донести все сувениры до рынка. Поэтому Петя хочет выбрать такое подмножество сувениров, что суммарный вес всех сувениров из подмножества не превышает m, а суммарная стоимость максимальна.
Помогите Пете определить максимальную суммарную стоимость.
В первой строке записаны два числа n и m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000) — кол-во сувениров у Пети и максимальный суммарный вес, который он сможет унести.
Далее следуют n строк, в i-й из них записаны два числа wi и ci (1 ≤ wi ≤ 3, 1 ≤ ci ≤ 109) — вес и стоимость i-го сувенира.
Выведите единственное число — максимальную суммарную стоимость сувениров, которые Петя сможет донести на рынок.
1 1
2 1
0
2 2
1 3
2 2
3
4 3
3 10
2 7
2 8
1 1
10
Название |
---|