408440: GYM103118 J Tuition Agent

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

For the $$$i$$$-th client, Piggy must make one of two choices:

1. Spend $$$X_i$$$ RMB training this client as a tutor;
2. Spend $$$Y_i$$$ 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 $$$K$$$ RMB in return. Of course, only those with higher rank can tutor those with lower rank. Note that $$$1$$$ is the highest rank. The $$$i$$$-th client has a unique number $$$R_i$$$ describing his grade rank, and no two clients have the same rank. 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 $$$T$$$ $$$(1 \le T \le 10)$$$ – the number of testcases.

For each testcase, the first line contains $$$2$$$ integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 100000, 0 \le k \le 10000)$$$ – the number of clients and the money Piggy can collect.

The next $$$n$$$ lines describe all the clients, where the $$$i$$$-th line contains three integers $$$R_i, X_i, Y_i$$$ $$$(1 \le R_i \le n, 0 \le X_i, Y_i \le 10000)$$$.

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