Time Limit: 2 Seconds
Memory Limit: 65536 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.
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
where the name is a string of no more than 30 characters other than '[' and
Process to the end of file.
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.
[AA] 1 7
[HH] 5 16
[EE] 6 8
[AA] 1 7
[HH] 5 16
[FF] 3 8
[DD] 4 6
The maximum power needed is 19 Watts.
The power will be out at time 5 because the power is 26 Watts and overloaded.
Author: ZHOU, Ran
Source: ZOJ Monthly, December 2003