A. Дело о матрешках
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андроид Андреид — известный на всю галактику детектив. Сейчас он расследует дело о вандализме на выставке современного искусства.

Главный экспонат выставки — конструкция из n матрешек — кукол, которые можно вкладывать друг в друга. Матрешки пронумерованы от 1 до n. Матрешку с меньшим номером можно вложить в матрешку с большим номером, при этом две матрешки не могут вкладываться непосредственно в одну и ту же матрешку, но возможны цепочки вложения, например, 1 → 2 → 4 → 5.

За одну секунду можно произвести любую из двух следующих операций.

  • Если есть матрёшка a, никуда не вложенная, и матрёшка b, причём b не содержит никаких матрёшек и не вложена ни в какую другую матрёшку, можно поместить a в b;
  • Если матрёшка a непосредственно содержится в матрёшке b, причём b не вложена ни в какую другую матрёшку, можно достать a из b.

Согласно современным эстетическим нормам матрешки на выставке были собраны в определенной конфигурации, то есть в виде нескольких отдельных цепочек вложенных матрёшек, однако преступник, следуя загадочному плану, разобрал все матрёшки и собрал их в одну большую цепочку (1 → 2 → ... → n). Для продолжения расследования Андреиду необходимо узнать, за какое минимальное время это возможно сделать.

Входные данные

В первой строке даны целые числа n (1 ≤ n ≤ 105) и k (1 ≤ k ≤ 105) — количество матрешек и цепочек матрёшек в изначальной конфигурации.

В следующих k строках даны описания цепочек: в i-й строке сначала идет число mi (1 ≤ mi ≤ n), а затем mi чисел ai1, ai2, ..., aimi — номера матрешек в цепочке (матрёшка ai1 вложена в матрёшку ai2, которая вложена в матрёшку ai3, и так вплоть до матрёшки aimi, которая не вложена ни в какую другую матрёшку).

Гарантируется, что m1 + m2 + ... + mk = n, номера всех матрешек во всех цепочках различны, в каждой цепочке номера матрешек идут по возрастанию.

Выходные данные

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

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

В первом тесте из условия есть две цепочки: 1 → 2 и 3. За одну секунду можно вложить первую цепочку во вторую и получить 1 → 2 → 3.

Во втором тесте из условия требуется разобрать все три цепочки на отдельные матрёшки за 2 + 1 + 1 = 4 секунды, и собрать из них одну большую цепочку за 6 секунд.