Выбор по одному из каждой группы


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

Сложность: 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

Комментарии

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