Description

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

Format

Input

输入的第$1$行是测试用例的数量。每个测试用例的第1行都包含两个整数$n$和$k（1≤k≤n≤200）$。接下来的$n$行，每行都包含三个整数$a_i、b_i、w_i（1≤a_i<b_i≤100000，1≤w_i≤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