Автор: | И. Блинов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Прораб распланировал работы на n дней вперёд, в день i выполняется только один тип работ ai и при этом требуется ci работников. В компании нет постоянных сотрудников, каждый день нанимаются новые работники для выполнения работ.
Так же у прораба имеется список из m работников. j-й работник имеет компетенции на kj различных работ и работник просит pj денег за один день работы (в независимости от типа выполняемых работ).
Так как бюджет ограничен, прораб хочет узнать какое минимальное количество денег он может потратить в каждый из n дней при этом наняв нужное количество работников. Гарантируется, что работников всегда достаточно.
Первая строка входного файла содержит два целых числа n и m. Далее следует n строк содержащих по два целых числа ai и ci. Следующие m строк содержат два целых числа kj и pj, количество компетенций и зарплата за день сотрудника с номером j, далее в этой строке идут kj чисел, номера работ которые может выполнять сотрудник с номером j.
Выходной файл должен содержать n целых чисел, i-e число минимальное количество денег которое нужно потратить в день i.
0≤n,m,ki≤105; 1≤ai≤109; 1≤pi≤100
Сумма по всем ki не превосходит 2⋅105.
Решения работающие для 0≤n,m,ki≤103; 1≤ai,pi≤103, сумма по всем ki не превосходит 2⋅103 оцениваются из 40 баллов.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|