После вечеринки в трактире «Гарцующий пони» хоббиты расходились по домам. На первом перекрёстке вся компания разделилась на несколько групп, каждая из которых пошла своей дорогой. Разумеется, соблюдая правила хорошего тона, хоббиты перед расставанием обменялись рукопожатиями (каждый хоббит пожал руку каждому, с которым он расставался, вне зависимости от пола). Каждая группа, дойдя до следующего перекрёстка, в свою очередь разделилась на меньшие группы, также обменявшись рукопожатиями. Этот процесс продолжался до тех пор, пока все холостые хоббиты и супружеские пары не разошлись по домам. Другими словами, группы разбивались до тех пор, пока не осталось ни одной группы из трёх и более хоббитов. Ваша задача — подсчитать количество сделанных рукопожатий.

Пронумеруем группы хоббитов так, что первая (та, которая вышла из трактира) получит номер 1, а все остальные — различные последовательные номера от 2 и далее. В первой строке записаны два числа N и K — общее количество хоббитов, вышедших из трактира и количество супружеских пар. Эти числа удовлетворяют ограничениям: 2 < N ≤ 20000; 0 ≤ 2K ≤ N. В каждой следующей строке записан номер группы, затем — количество групп, на которые она разбивается, потом идут пары чисел, разделенные пробелами — номер и численность каждой новой группы. Гарантируется, что если группа Y получилась в результате разбиения группы X, то описание разбиения группы X будет раньше описания разбиения группы Y. Это, в частности, означает, что описание группы 1 расположено во второй строке. Если группа Y получилась в результате разбиения группы X, но её описания не последовало, — это означает, что группа Y больше не разбивалась.

Выведите количество сделанных рукопожатий.