
134  ZOJ Monthly, June 2014  I
Left 4 Dead (abbreviated as L4D) is a cooperative firstperson shooter arcadestyle video game. Each player controls a survivor. They play through the levels fighting off the infectedliving humans who have been infected with a rabieslike virus that causes psychosis. Each level has a distance and a difficulty factor. Your performance can be measured by scores. To simplify the problem, there are two survivors called Bill and Zoey in this game. They walk one meter per second. The scores consists of two parts: the sum of distance scores of each survivor and the bonus score. If a survivor reaches the destination, his distance score is 100. Otherwise, the distance score is the percentage of the distance the survivor finishes to the total distance. Bonus scores can be calculated by following formula: score = (difficulty factor) * (total HP) * (number of survivors who reaches the destination). The total score should be rounded down to integer. Each survivor has 100 HP at the beginning. In order to treat the wounds, they can use the pill or injection. A pill adds 50 HP and a injection adds 25 HP. Each survivor can carry at most one pill and at most one injection, but the pills and injections can be shared. They can use these pills order injections at any time they want. In addition, the survivor's HP can go beyond 100, but it can not exceeds 200. If a survivor's HP is more than 100, his HP will decrease 1 per second until his HP reduced to 100. If a survivor's HP reach 0, he will dead, forever. Bill and Zoey starts their journey, but there are many infected persons on the way. To escape from the ith infected person, one of the survivors need to receive some damage. Under this situation, they want to know the maximum score they would have. Please help them. InputThere are multiple test cases. For each test case: The first line contains four integers F (1 <= F <= 5), D (1 <= D <= 10 ^ 6), N (0 <= N <= 10), M (0 <= M <= 10), indicating the difficulty factor, the total distance, the number of infected persons, the number of pills or injections on the road. The following N lines contains two integers PX_{i} (0 < PX_{i} < D), PT_{i} (1 < PT_{i} <= 200). It means at PX_{i} meters from the starting point, there is a infected persons which will cause PT_{i} damage. The next M lines contains two integers RX_{i} (0 < RX_{i} < D), RT_{i} indicating at RX_{i} meters from the starting point, there is a pill (RT_{i} = 1) or a injection (RT_{i} = 2). The PX_{i} and RX_{i} will sorted in increasing order, respectively. OutputFor each test case, output the maximum score the survivors can get. Sample Input2 100 2 1 3 100 5 40 3 1 Sample Output640 HintThe survivor can pick and use the pill at X = 3 first, then fight with the infected person to avoid being killed. Author: GAN, Tiansheng 