Задача C. Найм рабочих

Автор:И. Блинов   Ограничение времени: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
5 3
1 1
2 1
3 1
1 3
1 2
3 100 1 2 3
3 10 1 2 3
1 1 1
1
10
10
111
11
2
1 4
229 4
2 23 1 229
2 22 4 229
2 11 229 15
3 21 65 43 229
77

0.073s 0.014s 13