405173: GYM101810 A Careful Thief

There are consecutive buildings numbered from 1 to 10⁹ each of which has an amount of money in it. The money is given in the form of m non-overlapping segments, in which each segment i has 3 values: l_i, r_i, and v_i, meaning that each building with number x (l_i ≤ x ≤ r_i) has v_i amount of money.

A thief came to rob the city, however, this thief does not want to get caught, so he can only rob at most k consecutive buildings, such that if he starts robbing buildings from building z, he can rob all buildings in the range inclusive.

Your task is to find the maximum amount of money the thief can collect. Can you?

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains two integers m and k (1 ≤ m ≤ 10⁵, 1 ≤ k ≤ 10⁹), in which m is the number money segments, and k is the maximum number of consecutive buildings the thief can rob.

Then m lines follow, giving the description of money segments. Each segment i is represented by 3 integers l_i, r_i and v_i (1 ≤ l_i ≤ r_i ≤ 10⁹, 1 ≤ v_i ≤ 10⁹), in which l_i and r_i are the boundaries of the segment, and v_i is the amount of money in each building in that segment.

The sum of m overall test cases does not exceed 2 × 10⁶.

For each test case, print a single line containing the maximum amount of money the thief can collect by robbing at most k consecutive buildings.

1
2 5
1 5 1
7 11 1

5