Задача D. Реорганизация авиакомпании ≡

Условие

На данный момент авиаперевозчик Аэроплот имеет парк из 2 ⋅ N самолётов. Руководство компании Аэроплот решило провести реорганизацию компании, а именно разделить компанию на две с парком в N самолётов каждая. Одна из компаний будет иметь прежнее название Аэроплот, а другая получит название Беда, и будет предоставлять услуги авиаперевозок по сниженным тарифам.

При разделении самолётов между авиакомпаниями должны выполняться следующие требования:

1. Каждый самолёт компании Аэроплот должен иметь уровень комфорта как минимум k.
2. Каждый самолёт компании Беда должен иметь уровень комфорта меньше чем k.

Для каждого из 2 ⋅ N самолётов известен список доступных пассажиру опций, всего p_i опций для самолёта с номером i. Опция номер j увеличивает суммарный комфорт самолёта номер i на a_ij. Уровень комфорта самолёта с номером i — это сумма значений доступных в нём опций.

Руководство ещё не определилось со значением k и просит вас посчитать для M различных значений k минимальное количество опций, которые следует удалить из всех самолётов суммарно, чтобы самолёты можно было разделить между двумя авиакомпаниями, чтобы выполнить перечисленные условия.

Формат входного файла

Первая строка входного файла содержит целые числа N и M. Далее следует 2 ⋅ N строк, описания самолётов. Первое целое число в строке p_i — количество опций самолёта с номером i, далее следует p_i целых чисел a_ij — опции самолёта i. Далее следует M целых чисел k_i.

Формат выходного файла

Выходной файл должен содержать M целых чисел — минимальное количество опций, которые нужно удалить из всех самолётов суммарно для каждого из заданных k_i. Если для какого-то k_i невозможно разделить самолёты заданным способом, следует вывести −1.

Ограничения

1 ≤ p_i, a_ij ≤ 1000; 1 ≤ 2 ⋅ N ≤ 2000; 1 ≤ M ≤ 10000; 1 ≤ k_i ≤ 10⁶;

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

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

1 3
1 10
2 5 5
1 
5
10

1
1
1

2 3
5 1 1 1 1 1
3 1 1 1
1 100
2 4 3
4
200
1

1
-1
3