2844. Emergency Mission
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 31 Accepted Runs: 12
Military Briefing
14th TFS / 9th AESOG
Airfield Flash
Time: 1130 local time
Mission:
Airfield Flash is ordered to do a cargo transfer.
Execution:
You will transfer important cargoes from N aeroplanes to M trucks. Take care about them, and do the job as soon as possible.
Expected Enemy Forces:
It is reported a U-2S is scouting nearby. Don't make the cargoes detected, transfer them inside rooms.
Allied Support:
Su-27s will fly DCA around Airfield Flash.
Situation:
All the aeroplanes and trucks are ready. Cargoes are packed in bricks, so they can be easily pick up or drop at any position on the route by forklifts. Unfortunately, there is only one forklift left in the airfield which can take K bricks at maximum. The initial and final location of the forklift is position O. An example of ground plan of the airfield is shown in the following figure. You need find an optimal route solution to minimize the total distance (and time).
Input
There are several test cases in the input. Each test case has three parts. The first is a line of three integers N, M and K (1 ≤ N, M, K ≤ 100). The second part includes N lines with three integers each: PAi, LAi, CAi (1 ≤ PAi, LAi, CAi ≤ 10000). PAi indicates the length from position O to the gate in the corridor. LAi indicates the length from the corridor to aeroplane Ai. CAi denotes the number of bricks in the aeroplane to transfer. The third part includes M lines with three integers each: PTi, LTi, CTi (1 ≤ PTi, LTi, CTi ≤ 10000). The first two integers represent the location of the truck Ti, and the last integer indicates its capacity.
The input ends when N equals zero. You may assume the sum of capacities of all the trucks is equal to the total bricks in aeroplanes to transfer.
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
2 3 3
3 3 5
10 1 5
4 3 4
7 1 3
8 2 3
0 0 0
Sample Output
60
Hint
One possible route for the sample input:
(1) Move to A1, pick up 3 bricks.
(2) Move to T1, drop 3 bricks.
(3) Move to A1, pick up 2 bricks.
(4) Move to T1, drop 1 bricks.
(5) Move to A2, pick up 2 bricks.
(6) Move to T3, drop 3 bricks.
(7) Move to A2, pick up 3 bricks.
(8) Move to T2, drop 3 bricks.
(9) Move back to Position O.
Problem Setter: Hill
