Выбор по одному из каждой группы
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
1.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Выбор по одному из каждой группы
Улан собирает набор из товаров, разбитых на g групп. Из каждой группы можно взять не более одного товара. У товара вес w и ценность v. Суммарный вес не должен превышать W. Какова наибольшая суммарная ценность?
Ввод. В первой строке g и W (1 ≤ g ≤ 50, 1 ≤ W ≤ 5000). Далее g строк: в каждой сначала число товаров s (1 ≤ s ≤ 5), затем s пар w и v (1 ≤ w ≤ 5000, 1 ≤ v ≤ 1000).
Вывод. Наибольшая суммарная ценность.
Пример
Ввод:
2 7
2 3 10 5 15
2 2 8 4 11
Вывод:
23
Комментарии