Рюкзак торговца яками


Отправить решение Решать в редакторе

Сложность: 38%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Рюкзак торговца яками

Торговец собирает в дорогу товары. Есть n видов товаров, каждый — в единственном экземпляре: i-й весит wᵢ кг и приносит vᵢ сомов прибыли. Як выдержит не больше W кг. Какую наибольшую суммарную прибыль можно увезти?

Формат ввода

В первой строке записаны n и W (1 ≤ n ≤ 200, 1 ≤ W ≤ 5000). В следующих n строках записаны wᵢ и vᵢ (1 ≤ wᵢ ≤ 50, 1 ≤ vᵢ ≤ 10⁶).

Формат вывода

Выведите наибольшую суммарную прибыль.

Пример 1

Вход:

3 5
2 30
3 40
4 50

Выход:

70

Комментарии

Еще нет ни одного комментария.