C. Cemetery Manager @ USU Internal Contest March'2003 @ Timus Online Judge

C. Cemetery Manager

Time limit: 1.0 second
Memory limit: 64 MB

There is a tradition at the USU championships to call the most hard-to-solve problems coffins. But to distribute coffins is also a very difficult problem. Consider a cemetery with places arranged in the form of a rectangle having N rows and M columns (1 ≤ N, M ≤ 100). At the initial moment of time the cemetery is empty. Incoming coffins are put in the row with empty places that has a minimal number; if there are several empty spaces in this row, then the column with the minimal number is chosen. From time to time the cemetery's clients are visited by their living relatives; it is considered to be a pleasure for the clients. But it's only a headache for the cemetery manager, since because of these visitors he cannot give to new clients places that have been used. Happily, visitors are not perfect, so after some time they forget where their relatives have been lying. That is why if a client was not visited for more than successive 1000 days, then on the 1001st day the manager regards the grave as empty. However, relatives of the adjacent clients (of those for whom the differences in the numbers of rows and columns are not greater than 1) may notice strange changes, so the manager puts a new client on a used place only if all the neighboring graves have not been visited for the last 100 days (this is a period of time sufficient for a neighbor's relatives to forget who was lying next to him or her). If, notwithstanding all the efforts of the manager, there is no place where he can put a new client, then the client is sent to a crematorium.

We have a complete list of arriving clients and coming visitors for some period starting from the foundation of the cemetery. Basing on this information, you should determine how many clients have been sent to a crematorium.

Input

The first input line contains numbers N and M that describe the size of the cemetery. Each of the next lines describes an event. A description starts with the time of the event measured in days (it can be from 0 to 7600). Then the type of the event is given: either d (arrival of a new client) or v (a visit of relatives) followed with the number of the client who has visitors. It is guaranteed that in the case of visit the client with such number was described in the input earlier.

The events are ordered according to their time. The input contains not more than 15000 events, and not more than 10000 of them describe arrivals of new clients.

Output

Output the number of clients that have been sent to a crematorium.

Sample

input	output
2 2 1 d 1 d 1 d 1 d 300 d 500 v 2 1001 d 1002 d 1002 d 1003 v 3 1003 d 1003 d 1236 v 2 2032 v 2 2033 d	3

Notes

Each tomb has up to 8 neighbors.
If a client was buried on day T then the tomb may be dug over on day T+1001 and may not be dug over on day T+1000.
If a tomb was visited on day T then its neighbors may be dug over on day T+101 and may not be dug over on day T+100.
A tomb is dug over as soon as there is an opportunity (see items 2 and 3).
During a funeral relatives notice nothing including the neighbors.
The clients are numbered in the the order that they arrive (including those who was sent to crematorium).
If there is already no tomb or the client has been sent to the crematorium immediately then a visit affects nothing.
The next in turn client may be always burried in an empty tomb inspite of the neighbor tombs visits (the neighbors' relatives wouldn't be surprised having found out that the adjacent empty tomb is already occupied).

Problem Author: Stanislav Vasilyev
Problem Source: Open collegiate programming contest for student teams, Ural State University, March 15, 2003