ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат школьников. Март 2002

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Рукопожатия

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

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
3 0
1 2 2 2 3 1
2 2 4 1 5 1
3
Автор задачи: Леонид Волков
Источник задачи: V командное первенство школьников по программированию (2 марта 2002)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1194. Рукопожатия