2015
04-16

# How Far Can Drive At Most

Now I am going to drive on a street. The street is a straight line. It will cost me one unit oil per meter. And my car can contain V units at most. Unfortunately some zones of the street have been damaged badly. The number of damaged zones is Q. One zone is represented as (l, r, C), means the zone between l to r is damaged, and it will cost me another C units of oil per peter. Please notice that zones may intersect. My question is how far can I drive at most.

Several cases(cases <= 10). The first line is the case number T. Then T cases follow. For each case : First line two integers l (indicating the length of the street) and V (indicating the amount of oil my car can contain at most when I start)(1 <= len, V <= 10 ^ 9). Second line of each case is an integer Q (0 <= Q <= 50000). Then Q lines follow, each with three integers (l, r, C), means the zone between l to r has been damaged and it will cost me another C units of oil per meter(1 <= l < r <= len, 1 <= C <= 100). (If you still can not understand the details, please see the hint.)

Several cases(cases <= 10). The first line is the case number T. Then T cases follow. For each case : First line two integers l (indicating the length of the street) and V (indicating the amount of oil my car can contain at most when I start)(1 <= len, V <= 10 ^ 9). Second line of each case is an integer Q (0 <= Q <= 50000). Then Q lines follow, each with three integers (l, r, C), means the zone between l to r has been damaged and it will cost me another C units of oil per meter(1 <= l < r <= len, 1 <= C <= 100). (If you still can not understand the details, please see the hint.)

2
100 100
2
10 20 5
10 30 14
1000 10000
3
10 20 4
10 30 14
10 15 5

14.50
1000.00
Hint
Hint:
In case 1, I can drive to 10 meters with total cost 10. Then as [10, 20] is covered by two zones, the cost of this zone if (1 +5 + 14) = 20 per meter.
So I candrive only 4.5 meters. And the answer is 14.50.
In case 2, I have so much oil that I can drive to the end of the road, and of course I can not drive farther. So the answer is 1000.00.