Captain is coding

To improve players’ coding skill, FJ collects a variety of problems and order the players to solve them. In order to ensure they can complete the task, FJ divides the problems into two collections and issues a deadline for each collection. He announces that anyone who can’t complete all the problems of any of the two collections before the deadline of it will be downgraded to be an alternative member.

Now we focus on Captain Chen. His coding skill can be qualified as an integer, which means the level of coding skill. The higher the level is, the faster and the more accurately Captain Chen codes. One has at least Ci level of coding skill is able to solve the ith problem. But after AC it, Captain Chen will get his coding skill increased by Di. Each hour, Captain Chen can either try to solve one problem, or just practice type. If he practices type for one hour, his coding skill will be increased by Z. Please notice that if he AC the same problem twice, the second AC won’t benefit him anymore. And if he chooses to practice or solve the problem, he will practice a whole hour.

Now, he wonders if he could solve all the problems on time. If he could, he also wonders the minimum time needed to accomplish this task.

Can you help Captain Chen?

The first line of the input contains a single integer T, indicating there are T cases.

In each case, the first line contains five integers N, the numbers of problems; X, the deadline of problems of collection A; Y, the deadline of problems of collection B; W, the initial coding level of Captain Chen; and Z, which was mentioned above. Next there are N lines, each describing one problem and containing two integers Ci and Di, which are mentioned above. Following the Ci and Di there is a character in each line. The character is either ‘A’ or ‘B’, indicating which collection the problem belongs to.

We guarantee that 0<N<=1000, 0<X, Y<=1000000, 0<Z<=1000, 0<=W<=10^9, 0<=Ci<=10^9, 0<=Di<=1000. Please notice that if the deadline of a problem is X, you can solve the problem in X hours but not X+1 hours.

There are about 1000 cases whose N is no more than 10, about 30 cases whose N is no more than 100, and no more than 5 cases whose N is larger than 100.

The output of each case contains a single line. If Captain Chen can solve all the problems before their deadline, this line should be the minimum time needed to do it, measured in hour. Otherwise just print “Poor Captain Chen”.

2
2 10 30 5 1
10 5 A
30 5 B
2 10 20 5 1
10 5 A
30 5 B

22
Poor Captain Chen

BUPT

2016 Multi-University Training Contest 10