После нескольких реформ в Берляндию стали гораздо чаще приезжать туристы, и многие жители Берляндии, смекнув, что в туристическом бизнесе можно очень неплохо заработать, решили сменить место работы. Петя, например, бросил работу в IT-фирме и стал продавать сувениры на рынке.
Как и всегда, этим утром Петя собрался на рынок. У Пети дома стоит n различных сувениров; i-й сувенир характеризуется своим весом wi и стоимостью ci. По предыдущим дням Петя понял, что, скорее всего, ему не удастся донести все сувениры до рынка. Поэтому Петя хочет выбрать такое подмножество сувениров, что суммарный вес всех сувениров из подмножества не превышает m, а суммарная стоимость максимальна.
Помогите Пете определить максимальную суммарную стоимость.
Выходные данные
Выведите единственное число — максимальную суммарную стоимость сувениров, которые Петя сможет донести на рынок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
2 1
|
0
|
|
2
|
2 2
1 3
2 2
|
3
|
|
3
|
4 3
3 10
2 7
2 8
1 1
|
10
|