Raining

There are N mountains represented by N Isosceles triangles above ground. We can assume that every adjacent mountain can shape a valley. When it rains, the rain will form a plane in the valley. Now let's make things a little easier by drawing the vertical profile of the actual mountains. You can get more details from the below figure.

When it rains, the quantity of water is proportional to the time that is raining and the length of the plane by which some valley can receive the water (in the figure 1, “l1” is the length of the plane). In the figure 1, v means the velocity of the rain (please see the figure for more details for the formula of the rain). If a valley is filled with rain, the water will overflow. According to the shape of the mountain, the water may flow to the left, or to the right. You can assume that the height of the different mountains are different. This outflow of water will fill the valley next to the current valley. You can get the more details from the Figure 2.
  
You will get the information of the mountain. Please output the time during which the mountains can be filled by the rain. After the time, the quantity of the water will not increase even if it still rains.

The first line of an input file consists of a single number denoting the number of test cases in the file. The number of cases is not more than 20.
  For each test case, the input format is as follows. The first line gives two integers N and V( 1<=N<=5000, 20<=V<=200). N is the number of the mountains and V is the velocity of the rain. For the next n lines, the ith line gives three integers Li, Ri, Hi( 0<=Li<Ri<=10^9, 1<=Hi<=2500000, i=1, 2, ... , N). li is the coordinate of the left bottom point of the ith mountain. And the ri is the right one. hi is the height of the ith mountain. You can assume that Li<=Ri-1.We guarantee that the valley exists between every two adjacent mountains. You can assume that the left coordinate of the i+1th mountain is strictly larger than the corresponding one of the ith mountain. Please mind that there may be such conditions like the figure 3.

For each test case, print the time we need. The number must be printed with 3 decimal digits. (The number must be rounded up or down according to the usual rounding rules.

2

2 3
0 2 1
1 5 2

5 3
0 26 37
17 59 35
48 81 79
77 123 77
106 212 33

0.042
11.384

The 36th ACM/ICPC Asia Regional Beijing Site —— Online Contest