Problem H. Intervals

时间限制 5000 ms   内存限制 64 MB

You are given N weighted open intervals. The ith interval covers (ai, bi) and weighs wi. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.

输入数据

The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ KN ≤ 200).
The next N line each contain three integers ai, bi, wi(1 ≤ ai < bi ≤ 100,000, 1 ≤ wi ≤ 100,000) describing the intervals.
There is a blank line before each test case.

输出数据

For each test case output the maximum total weights in a separate line.

样例输入

复制
4

3 1
1 2 2
2 3 4
3 4 8

3 1
1 3 2
2 3 4
3 4 8

3 1
1 100000 100000
1 2 3
100 200 300

3 2
1 100000 100000
1 150 301
100 200 300

样例输出

复制
14
12
100000
100301

提交

请先 登录

© 2025 FAQs Contact About