← К списку задач

Бесконечный рюкзак

Сложность: 8%

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

Настало время собирать вещи. Открыв шкаф, вы заметили, что у вас есть nn вещей, которые вам хотелось бы взять с собой. У каждой вещи есть по два показателя: wiw_i - вес и uiu_i - полезность.

К счастью, недавно за победу на школьном этапе Всероссийской Олимпиады Школьников вам подарили бесконечный рюкзак. Его особенность в том, что он может вместить любое количество вещей любого веса, т. е. у вас не будет никаких проблем при его носке, если сумма веса вещей в нём \le \infin.

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

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

В первой строке записано число nn - количество вещей в шкафу (1n300)(1 \le n \le 300). Далее идут nn строк, где в ii-той строчке через пробел записаны два числа ww и uu – параметры ii-той вещи (1w,u100)(1 \le w, u \le 100).

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

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

Подзадачи

баллынеобх. подзадачиограничения
1

20

-

n10n \le 10

2

30

-

nn - число Фибоначчи

3

50

1, 2

Нет дополнительных ограничений

STDINSTDOUT
10
17 31
42 42
9 1
2 3
45 1
1 45
88 87
12 16
91 23
10 10
259