Welcome to ZOJ
134 - ZOJ Monthly, June 2014 - I
Left 4 Dead

Time Limit: 4 Seconds      Memory Limit: 131072 KB

Left 4 Dead (abbreviated as L4D) is a cooperative first-person shooter arcade-style video game. Each player controls a survivor. They play through the levels fighting off the infected-living humans who have been infected with a rabies-like 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 i-th 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.


There 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 PXi (0 < PXi < D), PTi (1 < PTi <= 200). It means at PXi meters from the starting point, there is a infected persons which will cause PTi damage. The next M lines contains two integers RXi (0 < RXi < D), RTi indicating at RXi meters from the starting point, there is a pill (RTi = 1) or a injection (RTi = 2).

The PXi and RXi will sorted in increasing order, respectively.


For each test case, output the maximum score the survivors can get.

Sample Input

2 100 2 1
3 100
5 40
3 1

Sample Output



The survivor can pick and use the pill at X = 3 first, then fight with the infected person to avoid being killed.

Author: GAN, Tiansheng
Submit    Status