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

Условие

Прораб распланировал работы на n дней вперёд, в день i выполняется только один тип работ a_i и при этом требуется c_i работников. В компании нет постоянных сотрудников, каждый день нанимаются новые работники для выполнения работ.

Так же у прораба имеется список из m работников. j-й работник имеет компетенции на k_j различных работ и работник просит p_j денег за один день работы (в независимости от типа выполняемых работ).

Так как бюджет ограничен, прораб хочет узнать какое минимальное количество денег он может потратить в каждый из n дней при этом наняв нужное количество работников. Гарантируется, что работников всегда достаточно.

Формат входных данных

Первая строка входного файла содержит два целых числа n и m. Далее следует n строк содержащих по два целых числа a_i и c_i. Следующие m строк содержат два целых числа k_j и p_j, количество компетенций и зарплата за день сотрудника с номером j, далее в этой строке идут k_j чисел, номера работ которые может выполнять сотрудник с номером j.

Формат выходных данных

Выходной файл должен содержать n целых чисел, i-e число минимальное количество денег которое нужно потратить в день i.

Ограничения

0 ≤ n, m, k_i ≤ 10⁵; 1 ≤ a_i ≤ 10⁹; 1 ≤ p_i ≤ 100

Сумма по всем k_i не превосходит 2 ⋅ 10⁵.

Описание подзадач и системы оценивания

Решения работающие для 0 ≤ n, m, k_i ≤ 10³; 1 ≤ a_i, p_i ≤ 10³, сумма по всем k_i не превосходит 2 ⋅ 10³ оцениваются из 40 баллов.

Примеры тестов

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

1 4
229 4
2 23 1 229
2 22 4 229
2 11 229 15
3 21 65 43 229

77