C. Дефрагментация

В новой файловой системе дисковое пространство разделено на N кластеров одинакового размера, нумерующихся числами от 1 до N. Каждый файл занимает один или несколько кластеров. Все кластеры, не занятые файлами, считаются свободными.
Файл считывается с диска более быстро, если он расположен в последовательных кластерах по порядку.

Все файлы перенумерованы натуральными числами от 1 до K в порядке убывания частоты обращения. Так как считывание с начала диска выполняется быстрее, чем считывание с конца, оптимальным является расположение, при котором файл номер 1 занимает кластеры 1..S1, файл номер 2 - кластеры S1+1,.., S1+ S2 и т.д. (здесь Si - это число кластеров, занимаемое i-ым файлом).

Для того, чтобы расположить файлы оптимальным образом, производятся операции перемещения кластеров. Каждая такая операция заключается в чтении одного занятого кластера с диска в память и переписывание его содержимого в какой-либо свободный кластер. После этого первый кластер объявляется свободным, а второй - занятым.

Вашей целью является расположить файлы на диске оптимальным образом, сделав минимальное количество операций перемещения кластеров.

Входные данные
Первая строка входного файла содержит числа N и K (1≤K<N≤10000).
В i+1 строке (1≤i≤K) находится описание i-го файла. Первым числом в строке является Si (1≤Si≤N) - число кластеров в файле, далее следуют Si чисел, которые являются номерами кластеров по порядку, в которых расположен файл.
Номера всех кластеров во входных данных различны, и на диске есть хотя бы один свободный кластер.

Входные данные
Последовательность операций перемещений кластеров. Каждая операция задаётся парой чисел P и Q, где данные перемещаются с кластера P в кластер Q.

Пример входного и выходного файлов
INPUT.TXT OUTPUT.TXT 
20 3
4 2 3 11 12
1 7
3 18 5 10
  
2 1
3 2
11 3
12 4
18 6
10 8
5 20
7 5
20 7