Description

给定$n$个加权开放区间，第i个区间覆盖$(ai,bi)$，权值为$wi$。选择一些区间，在实轴上没有点被覆盖超过$k$次的限制下，使总权值最大化。

Format

Input

输入的第$1$行是测试用例的数量。每个测试用例的第1行都包含两个整数n和$k（1≤k≤n≤200）$。接下来的$n$行，每行都包含三个整数$ai、bi、wi（1≤ai<bi≤100000，1≤wi≤100000）$，用于描述区间。在每个测试用例前面都有一个空行。

Output

对每个测试用例，都单行输出最大总权值。

Samples

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

来源

POJ3680