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.


1. 怎么不说犹太人是东方中国的后裔啊？现在很是奇怪，怎么会有这么多所谓专家说什么古中国人是白种人，是贵族，黄皮白心的剑人，还有这么多人热烈的吹捧他们。搞搞清楚，你自己现在已经是黄种人了，再吹捧白种人也不能把你的基因变成白种人的基因。