Golf Courses

We want to build golf courses near the New Light apartment complex. Several candidate sites have been surveyed, and for each candidate we know its capacity (the number of clients it can serve) and its construction cost.

Many residents of New Light want to play golf. We must choose some of the candidate sites, build golf courses on them, and assign every client to one of the built courses so that all clients are served, while making the total cost as small as possible.

The total cost has two parts:

• the total connection cost of the clients to the courses they use, plus
• the total construction cost of the courses that are built.

Consider the example below.

The links between the candidate sites and New Light form a star graph: New Light is the center vertex, and every other vertex is a candidate site. The number next to New Light is the number of clients who want to play golf. The two numbers next to a candidate site are its construction cost and its capacity. The number on an edge is the distance between New Light and that candidate site; a client who uses that course pays this distance as a connection cost.

For this example, the optimal solution is shown below. Two courses are built, with construction costs $6$ and $2$. Two clients use the course whose connection cost (distance) is $1$, and the remaining three clients use the course whose connection cost is $2$. The total construction cost is $6 + 2 = 8$, and the total connection cost is $1 + 1 + 2 + 2 + 2 = 8$, so the total cost is $8 + 8 = 16$.

In the examples, the first test case corresponds to the figures above.

The input is read from standard input and consists of $T$ test cases. The first line contains the number of test cases $T$ ($1 \le T \le 20$).

Each test case has the following form. The first line contains a positive integer $N$ ($1 \le N \le 500$), the number of candidate sites. The second line contains a positive integer $P$ ($1 \le P \le 10000$), the number of clients. Each of the next $N$ lines describes one candidate site with three positive integers separated by single spaces: the distance from New Light to the site, the construction cost of the course, and the capacity of the course. Every integer is between $1$ and $10000$, inclusive.

The total capacity of the candidate sites is at least $P$, so all clients can always be served.

Write to standard output. For each test case, print on its own line the minimum possible total cost, that is, the smallest achievable sum of the total connection cost and the total construction cost.