1-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"D" Менеджер памяти
Ограничение по времени 3 секунды
Ограничение по памяти 256 мегабайт

Петя активно ведет разработку своего собственного менеджера памяти MEM 2.0 для хранилища на базе магнитных 7D блоков. Однако он столкнулся с проблемой оптимальной выдачи данных из хранилища пользователям.

Всего в менеджере Пети хранится n блоков с данными, пронумерованных от 1 до n, и имеется q запросов о выдаче данных с одного или нескольких из них. Запросы необходимо обработать в том порядке, в котором они поступили.

Для выдачи данных у Пети есть k указателей, каждый из которых указывает на один из блоков. Изначально Петя может поставить указатели на любой набор блоков.

Петин менеджер умеет мгновенно выдавать данные из любого числа блоков, если на каждый из них указывает хотя бы один указатель. Если же это не так, менеджер сначала переставляет указатели, чтобы условие выполнялось, а затем выдает данные — время выполнения этой операции для i-го запроса составляет si миллисекунд, можно переставить любое число указателей.

Петя хочет реализовать переставление указателей в менеджере так, чтобы суммарное время ответа на все запросы пользователей было минимальным. Запросы необходимо обработать в том порядке, в котором они поступили, менять местами запросы нельзя. Помогите ему.

Рассмотрим приведенные в примере тесты.

В первом тесте Петя изначально может поставить указатели на блоки 1, 2 и 4 — после этого первые два запроса выполнятся мгновенно. Перед третьим запросом за s3 = 1 миллисекунду он может поставить указатели на блоки 2, 3 и 5, а перед четвертым запросом за s4 = 1 миллисекунду он может поставить указатели на блоки 1, 3 и 5. Суммарное время на все запросы будет равно s3 + s4 = 2 миллисекунды.

Во втором тесте Пете невыгодно выполнять первые два запроса мгновенно (ставя изначально указатели на блоки 1, 2 и 4), потому что потом ему придется потратить 10 миллисекунд, чтобы поставить указатели на другие блоки. Поэтому оптимальная стратегия для Пети — изначально поставить указатели на блоки 1, 2 и 3, перед вторым запросом на блоки 1, 3, 4 за s2 = 1 миллисекунду, а перед последним запросом поставить указатели на блоки 1, 3 и 5 за s4 = 3 миллисекунды. Итого суммарное время ответа на запросы s2 + s4 = 4 миллисекунды.

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 1000).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержатся три числа n, k, q — количество блоков в менеджере, количество указателей и количество пользовательских запросов соответственно (1 ≤ k ≤ n ≤ 105, 1 ≤ q ≤ 106).

В следующей строке содержится q целых чисел si — время, требуемое для перестановки указателей при ответе на i-й запрос (1 ≤ si ≤ 104).

В следующих q строках содержится описание запросов пользователей, i-й запрос описывается одной строкой, где первое число ci описывает количество блоков данных, которое пользователь хочет получить (1 ≤ ci ≤ k), а следующие ci чисел описывают номера этих блоков bi, j в возрастающем порядке (1 ≤ bi, j ≤ n).

Гарантируется, что сумма n во всех тестах одних входных данных не превосходит 105, а также сумма ci во всех тестах одних входных данных не превосходит 106.

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

Для каждого теста выведите ответ на него — минимальное суммарное время ответа на все запросы пользователей.

Примеры
Входные данные
2
5 3 4
1 1 1 1
1 2
2 1 4
2 2 3
3 1 3 5
5 3 4
1 1 10 3
1 2
2 1 4
2 1 3
3 1 3 5
Выходные данные
2
4
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.