Piggy is a selfless tuition agent. He already has potential clients.

For the -th client, Piggy must make one of two choices:
 Spend  RMB training this client as a tutor;

 Spend  RMB making the client become a student who needs tutoring.

If Piggy can match a tutor with a student for one-on-one tutoring, he can earn  RMB in return. Of course, only those with higher rank can tutor those with lower rank. Note that is the highest rank. The -th client has a unique number describing his grade rank, and no two clients have the same rank.

Note that because of limited energy, each client is in at most one pair.

Now, Piggy wants to know the maximum profit he can get (the profit could be negative).

输入描述:

The first line contains an integer   -- the number of testcases.

For each testcase, the first line contains  integers  and   -- the number of clients and the money Piggy can collect. The next  lines describe all the clients, where the -th line contains three integers  .

It is guaranteed that testcases are generated randomly.

输出描述:

For each test case, print the maximum profit Piggy can get.

2
4 2
1 2 2
4 1 2
3 1 1
2 4 4
6 8
4 4 1
6 5 6
1 2 7
2 3 4
3 1 1
5 8 7

-5
4