Так повелось, что самые нерешаемые задачи на олимпиадах УрГУ обычно называют гробами. А ведь распределять гробы — тоже очень сложная задача. Рассмотрим кладбище, могилы на котором расположены в форме матрицы из N строк и M столбцов (1 ≤ N, M ≤ 100). В начальный момент времени кладбище пусто, все могилы свободны. Поступающих нежильцов кладут в свободную могилу с минимальным номером строки, а если в этой строке несколько свободных могил, то выбирают ту из них, у которой минимальный номер столбца. Время от времени клиентов кладбища навещают живые родственники — считается, что клиентам от этого приятнее. Но менеджеру кладбища это приносит только расстройство — из-за этих посетителей он не может отдать старые площадки новым клиентам. К счастью, посетители — тоже люди, поэтому через некоторое время они забывают, где именно лежат их родственники. Поэтому если клиента не навещали больше 1000 дней подряд, то на 1001 день менеджер считает, что могилу уже можно освободить (и, если будет нужно, отдать это место новому клиенту). Правда, родственники соседних клиентов (тех, номера столбцов и строк которых отличаются не более чем на 1) могут обратить внимание на странные изменения обстановки, поэтому менеджер освобождает могилу, только если все соседние могилы не навещали в течении последних 100 дней (за такое время родственники соседей успевают забыть, кто лежал рядом). Если, несмотря на все усилия менеджера, на кладбище совсем не остаётся свободных мест, то он посылает клиента в крематорий.

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

В первой строке указаны числа N и M, определяющие размер кладбища. Каждая следующая строка описывает некоторое событие. Описание события начинается с времени в днях (лежит в пределах от 0 до 7600). Далее указывается тип события: либо d (поступление нового клиента), либо v (визит родственников) и порядковый номер клиента, к которому пришли. Гарантируется, что в случае визита клиент с таким номером был ранее описан во входных данных.

События упорядочены по времени. Общее количество новых клиентов и посещений не превосходит 15000, из них не более 10000 описывают появление новых клиентов.

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