Power Management

Time Limit: 1 Second    Memory Limit: 32768 KB

In summer the society will be lack of power supply. We know that if the electricity on some wires exceeds an exact value, it will be dangerous and maybe cause some destroy. So the power stations decide to limit the power supply for every factory. If some wires overload, the switch will be off automatically. But factories usually have a lot of equipments, So the leader want you to write a program to show whether the power of the factory will be out according to the plan of the use of equipments.

Input

The input has two parts. The first part of the input is an equipment list of a factory. First line of this part is a positive integer N (N <= 50000) of all the equipment that a factory has and followed by n lines to show the power of each equipment. The ith line shows the ith equipment's name and the power needed pi (pi < 500 in Watts). No two equipments has the same name. The second part of the input is the plans. First line of each plan is two non-negative integers K (K < 2500) and P (1 <= P < 800000). K is the count of records of the plan and P is the maximum power supply for this factory. The next K lines show the records. Each record has a string and two integers si and ei in order, which indicate the name of the equipment and the open, close time of this equipment (0 <= si < ei <= 32768). All the names will be given in the format
[NAME]
where the name is a string of no more than 30 characters other than '[' and ']'

Process to the end of file.

Output

The output of each plan is a sentence. If the maximum power needed will not exceed the power supply, you should output the exact value of the maximum power. Otherwise you should output the time when the power will be out and the exact power needed at that time. The format is shown in the sample.

Sample Input

8
[AA] 3
[BB] 4
[CC] 5
[DD] 6
[EE] 7
[FF] 8
[GG] 7
[HH] 9
3 20
[AA] 1 7
[HH] 5 16
[EE] 6 8
4 24
[AA] 1 7
[HH] 5 16
[FF] 3 8
[DD] 4 6

Sample Output

The maximum power needed is 19 Watts.
The power will be out at time 5 because the power is 26 Watts and overloaded.

Submit

Source: ZOJ Monthly, December 2003