你可能会注意到以下程序。它用于计算给定序列的某种代价。

calc_cost(a):
    current = 0
    cost = 0
    for (cost0, cost1, color) in a
        if current == 0
            cost += cost0 
        else
            cost += cost1
        current = color
return cost

对于一个由许多三元组 $(cost0, cost1, color)$ 组成的序列 $A$，其每个子序列都有一个通过该程序计算出的代价。

Alice 想要知道所有子序列中，代价第 $k$ 大的子序列的代价。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。

对于每个测试用例，第一行包含两个整数 $n$ 和 $k$，其中 $n$ 表示序列的长度。

接下来的 $n$ 行中，第 $i$ 行包含三个非负整数 $cost0$、$cost1$ 和 $color$，其中 $0 \le cost0, cost1 \le 10000$ 且 $0 \le color \le 1$，对应序列中的第 $i$ 个三元组。

我们保证该序列至少有 $k$ 个非空子序列。

所有测试用例中 $n$ 的总和不超过 $400000$，且所有测试用例中 $k$ 的总和不超过 $400000$。

输出格式

对于每个测试用例，在一行中输出答案。

样例

输入样例 1

1
3 4
2 1 0
1 3 1
3 1 1

输出样例 1

3

说明

代价最大的四个子序列如下：

• calc_cost({ A_1, A_3 }) = 5
• calc_cost({ A_1, A_2, A_3 }) = 4
• calc_cost({ A_1, A_2 }) = 3
• calc_cost({ A_3 }) = 3