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

Автор:И. Блинов, А. Жихарева   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ pi, aij ≤ 1000; 1 ≤ 2 ⋅ N ≤ 2000; 1 ≤ M ≤ 10000; 1 ≤ ki ≤ 106;

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

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

Подзадача Баллы Дополнительные ограничения
2 ⋅ N, Maijpi
1251 ≤ 2 ⋅ N, M ≤ 10001 ≤ aij ≤ 1000pi = 1
2251 ≤ 2 ⋅ N, M ≤ 1000aij = 1 1 ≤ pi ≤ 1000
3251 ≤ 2 ⋅ N, M ≤ 10001 ≤ aij ≤ 10001 ≤ pi ≤ 1000
4251 ≤ 2 ⋅ N ≤ 2000, 1 ≤ M ≤ 100001 ≤ aij ≤ 10001 ≤ pi ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 3
1 10
2 5 5
1 
5
10
1
1
1
2
2 3
5 1 1 1 1 1
3 1 1 1
1 100
2 4 3
4
200
1
1
-1
3

0.047s 0.008s 15