There are several cities and towers on a straight line. Towers can be set to connection-accepting by paying a cost. We are given the location (on the X-axis), of the towers and the cities. Our job is to set up certain towers as connection-accepting. Now every city, pays you an amount equal to D - distance_travelled_by_data, for every unit of data (for every tower) it can send. (distance_travelled_by_data = cityX - towerX); Our job here is to set up connections on different towers to get maximal profit.

Each city when it wants to route some data to a tower works with the following algorithm:

1. Find the nearest tower to the left of the city.
2. If it is within the range 'D', it sends the data to that tower. If this tower exceeds the range D, or if the tower doesn't accept connections, the city cant send the data and stops immediately. (Doesn't check the next available tower);
3. If the data is sent successfully: Then the city:
   • Skips three towers. (Doesn't care if these three towers are connection-accepting or not);
   • Tries to send data to the next tower (the fourth one after the skipping), by using step (2);

Input

Input consists of multiple testcases.

The first line of each test case contains three integers: D C T; the range, the number of cities and the number of towers, respectively.

The second line of each test case contains exactly C integers saying the location of the cities (on the X-axis).

The next T lines contain exactly two integers: location[i] connection-cost[i]; which is the position of tower i, and the cost to set up tower i as connection-accepting;

The input ends with a line: "-1 -1 -1"

Output

For each test case, output a single line saying the maximum amount of profit you can make.

Constraints

No two points (towers or cities), will have the same X-coordinate. T, C <= 100.

Sample

Input:
4 9 6
23
43
18
15
29
50
41
31
40
32 2
26 0
46 7
48 0
50 3
38 1
-1 -1 -1

Output:
5