Given a positive integer ∆ (0 < ∆ < 10000), which is called the overhead, and M (0 < M ≤ 200) straight line segments in a two-dimensional plane with the following properties: 1. each line segment has a height, which is a positive integer; 2. two line segments only intersect with each other on endpoints; 3. no two line segments are overlapped. Each line has a unique number between 1 and M. Each endpoint in the plane has a unique number between 1 and N (0 < N ≤ 400), where N is the total number of endpoints. A line segment is represented by its two endpoints (ni,nj). Let height(L) be the height of a line segment L. A path is a sequence of line segments LC1,LC2,...,LCk, such that k > 1, Ci ̸= Cj ∀i ̸= j, LCi intersects with LCi+1 for all 1 ≤ i < k, one endpoint of LC1 does not intersect with any other line segments, and one endpoint of LCk does not intersect with any other line segments. The cost between two intersection line segments i LCi and LCi+1 is height(LCi ) − height(LCi+1 ) That is, for example you can image, the number of stairs that one has to climb (up or down ) by walking from LCi to LCi+1. The cost of a path LC1,LC2,...,LCk is k−1 In the example shown in Fig. 1, ∆ = 25, M = 8, and N = 9. Then cost(L2, L3) = 1 and cost(L1, L6) = 8. L1, L4, L5 is not a path. There are three paths in the plane. The cost for the path L1, L6, L7, L8 is 109. The cost for the path L1, L4, L5, L8 is 131. The cost for the path L2,L3 is 51. Hence L2,L3 is the path with the least cost. You may also assume there is at least one path in the plane. Write a program to find the least cost among all paths. Input The first line is l, the number of test cases. The first three lines of test case #i are Mi , Ni and ∆i which are the numbers of line segments Fig. 1: An example of 8 straight lines with 9 endpoints. k · ∆ + ∑ i=1 cost(LCi , LCi+1 ).
2/2 and endpoints, and the overhead, respectively. The following Mi lines each contains the two endpoints of each line segment, starting from L1 to LMi , and its height. Each line segment is represented by three integers, separated by blanks. Output Contains l lines. The i-th line contains the least cost of all paths in the i-th test case. Sample Input 2 8 9 25 121 8 9 10 789 142 4 5 20 139 359 568 6 6 21 121 142 4 5 20 139 359 568 Sample Output 51 93