Now there is a problem for you to help a transportation company to finish the delivery task for face masks as soon as possible. Assume that all suppliers and consumers are located in a linear line such as railway or ship route. Suppliers (or consumers) have various supplying capacities (consuming requirements) for face mask. We use positive (or negative) integer to represent the capacity for supplier (or requirement for consumer). Moreover, the company has only one vehicle (train or ship), starting in location zero move back and force along the line to pick up and delivery all suppliers' products to all consumers on their requirements. Finally, the vehicle should move back to its initial location zero. In addition, the vehicle has a maximum capacity, so that the total amount of the face masks on the vehicle can not exceed its maximum capacity at any time.

We illustrate an example in the following figure. There are three suppliers S1, S2 and S3 that located in location -8, 0 and 2 respectively. The supplying capacity for each supplier is 3, 3 and 2. On the other hand, there are three consumers C1, C2 and C3 that located in location -5, -2 and 9 with the requirements -4, -2 and -2. The initial location of the vehicle (assume its maximum capacity is 3) is location 0.

One possible route of the vehicle to finish the task is:

(1) Pick up mask 3 at S2
(2) Move to C3, deliver mask 2 at C3
(3) Move to S3, pick up mask 2 at S3
(4) Move to C2, deliver mask 2 at C2
(5) Move to C1, deliver mask 1 at C1
(6) Move to S1, pick up mask 3 at S1
(7) Move to C1, deliver mask 3 at C1
(8) Move back to initial location 0

The total distance of the above route is 34.

If we input the locations, capacities (or requirements) of several suppliers (or consumers), would you mind help to find an optimal route solution to minimize the total distance of the route?

Input

There are several test cases in the input. Each test case has three parts. The first is a line of three integers S, C and P to represent the number of suppliers, the number of consumers and the maximum capacity of the vehicle (1≤S≤100, 1≤C≤100, 1≤P≤100), respectively. The second part includes S lines with two integers each. The first integer indicates the location of the supplier in the line, and the second one denotes its supplying capacity. The third part includes C lines with two integers each. The first integer represents the location of the consumer in the line, and the second integer indicates its requirement.

The input ends when P equals zero.

Note: Assume the sum of all supplying capacities is equal to the absolute value of the total consumer requirements in all test cases.

Output

For each case in the input, just output the minimum total distance of the optimal solution your program finds in one separate line.

Sample Input

3 3 3
-8 3
0 3
2 2
-5 -4
-2 -2
9 -2
0 0 0

Sample Output

34