Interval Revisited
题号：NC17338
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

Chiaki has a long interval [1,m] and n small intervals [l1, r1], [l2,r2], ..., [ln, rn]. Each small interval [li,ri] is associated with a weight wi.
Chiaki would to select some small intervals such that:
  • each integer position x ∈ [1, m] is covered by at least one small interval.
  • let sx be the sum of the weights of all the small intervals covering position x, the maximum value of sx should be minimum.
Chiaki would like to know the minimum value of maximum sx.

输入描述:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test
cases. For each test case:
The first line contains two integers n and m (1 ≤ n, m ≤ 2000) -- the number of small intervals and the length of the long interval.
Each of the next n lines contains three integers li, ri and wi (1 ≤ li ≤ ri ≤ m, 1 ≤ wi ≤ 1000).
It is guaranteed that the sum of all n does not exceed 20000.

输出描述:

For each test case, output an integer denoting the answer, or -1 if Chiaki cannot select such intervals.
示例1

输入

复制 
2
2 4
1 2 2
3 4 5
1 4
1 3 1

输出

复制 
5
-1