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 (t = 0) 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 friends and 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 friends 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 friends 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.
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 from the foundation of the cemetery. Then the type of the event is given: either d (arrival of a new client) or v (a visit of friends or relatives) followed with the number of the client who has visitors. 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.
The program should find the number of clients that have been sent to a crematorium.
500 v 2
1003 v 3
1236 v 2
2032 v 2
- Each tomb has 2 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 or there is no client with the required number 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