Сложность: 8%
Вы собираетесь переехать жить в горы – отвлечься от городкой суеты, оборвать все связи с интернетом и, любуясь пейзажами, придумать наконец полиноминальный алгоритм решения задачи о рюкзаке.
Настало время собирать вещи. Открыв шкаф, вы заметили, что у вас есть вещей, которые вам хотелось бы взять с собой. У каждой вещи есть по два показателя: - вес и - полезность.
К счастью, недавно за победу на школьном этапе Всероссийской Олимпиады Школьников вам подарили бесконечный рюкзак. Его особенность в том, что он может вместить любое количество вещей любого веса, т. е. у вас не будет никаких проблем при его носке, если сумма веса вещей в нём .
Ваша задача - взять с собой такой набор вещей, чтобы они вместились в рюкзак, а сумма их полезности была бы максимально возможной.
Входные данные
В первой строке записано число - количество вещей в шкафу . Далее идут строк, где в -той строчке через пробел записаны два числа и – параметры -той вещи .
Выходные данные
Выведите одно число - максимально возможную сумму полезности вещей, которые одновременно войдут в бесконечный рюкзак.
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 20 | - | |
2 | 30 | - | - число Фибоначчи |
3 | 50 | 1, 2 | Нет дополнительных ограничений |
STDIN | STDOUT |
10 17 31 42 42 9 1 2 3 45 1 1 45 88 87 12 16 91 23 10 10 | 259 |