Автор: | И. Блинов | Ограничение времени: | 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 |
|
|