1341 - A Simple Task

Time Limit: 1s Memory Limit: 128MB

Submissions: 422 Solved: 98
Description
As is known to all, lots of birds are living in HUST. A bird has s units of food on the first day, and eats k units of food each day. So they must find food in school or they will die. Because food is not that easy to find, birds store it home on the tree. If one bird runs out of food some day, he just dies. (It means that if the bird doesn't have enough food stored and can't find enough food that day, he will die.) A professor is researching on the birds. He has got some records of the birds' everyday life. And you, as his student, are to tell him the birds' state after the last day on the records of the bird.
Input
The first line is an integer, representing the number of test cases. In each case, the first line contains one integer n representing the number of records. The next line contains two integers -- s and k, representing the unit of food on the first day and the number of unit a bird needs each day. The next n lines, each contains a piece of record. The first word of each record is the name of a bird. You can assume that every bird has a distinct name and the name has no white space. The name has only alphabetical letters, i.e. A-Z and a-z. The following two integers is the date and the unit of food that the bird found on that day. (1<= n <=100000, the other integers are all greater than or equal to 1 and less than or equal to 10000.) Hint: the date of records may be disordered, but a bird's name will only appear once on each day. And the bird's name may appear even if he died before, so you can assume its the error in the records and just ignore it.
Output
Output "Case #t:" before each test case on a single line. For each test case, print out the name of all the birds and his food store, each bird a line. The output should be in alphabet order. If a bird died some day, you just tell the professor the bird was dead. The format is as the sample output. And you should check sample output for details. Output a blank line after each case.
Sample Input
3
3
100 3
Gaewah 4 3
Gaewah 10 5
Gaewah 100 1
1
5 10
Smith 1 3
4
10 5
peterpan 7 3
Oxford 3 5
Scheme 2 100
Regexp 1 10
Sample Output
Case #1:
Gaewah died.

Case #2:
Smith died.

Case #3:
Oxford 0
Regexp 15
Scheme 100
peterpan died.
Hint
Source
Xie Song