F. Hacked!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is planning on participating in TheForces round next week, a highly anticipated competitive programming contest where she aims to maximize her score by solving problems. However Bob, her rival, wants to minimize Alice's score by hacking her submissions during the contest.

The contest is scheduled to last for $$$T$$$ minutes and will consist of $$$n$$$ problems. The $$$i$$$-th problem will take Alice $$$t_i$$$ minutes to solve and yields $$$a_i$$$ points upon solving.

At the beginning of the contest, Alice will choose some problems that can be solved within the duration. However, Bob plans on hacking one of her solutions. He will be prepared to do so immediately after she has solved all her chosen problems and will do so in a way that minimizes Alice's final score.

If Alice is hacked on the $$$i$$$-th problem, she will lose the $$$a_i$$$ points she received for it. Fixing it will take an additional $$$f_i$$$ minutes. If she is able to fix it before the contest ends, she will recover the points but with a penalty $$$p_i$$$, i.e. she will only gain $$$(a_i - p_i)$$$ points. In case she is not able to fix it in time, she will not gain any points for the problem.

For example, consider the case when $$$n = 2$$$ and $$$T = 25$$$ and

  • $$$t_1 = 10$$$, $$$a_1 = 50$$$, $$$f_1 = 3$$$ and $$$p_1 = 25$$$
  • $$$t_2 = 10$$$, $$$a_2 = 60$$$, $$$f_2 = 5$$$ and $$$p_2 = 20$$$
Alice solves the first problem at $$$t = 10$$$ and the second problem at $$$t = 20$$$. Bob hacks the first problem. Alice fixes it by $$$t = 23$$$. In doing so Alice scores $$$(50 - 25) + 60 = 85$$$ points. If $$$T = 20$$$, Bob could hack the second problem and Alice would score $$$50 + 0 = 50$$$ points.

Note that Bob will make only one hack during the contest.

Alice knows that Bob will do this. Assuming they make their choices optimally, what is the maximum score Alice can get?

Input

The first line of each test case contains an integer $$$tc$$$ $$$(1 \leq tc \leq 200)$$$ — the number of test cases. The description of each test case is as follows.

The first line of each test case contains two integers $$$n$$$ and $$$T$$$ $$$(1 \le n, T \le 500)$$$ — the number of problems and the duration of the contest.

The next $$$n$$$ lines describe each problem. The $$$i$$$-th line contains four integers $$$t_i$$$, $$$a_i$$$, $$$f_i$$$ and $$$p_i$$$ $$$(1 \le t_i, f_i \le T, 1 \le p_i \le a_i \le 10^6)$$$ — the time needed to solve it, the points gained for solving it, the time needed to fix it if hacked, and the penalty received if it is fixed after it is hacked.

The sum of $$$n$$$ over all test cases does not exceed $$$500$$$. The sum of $$$T$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case, print a single integer — the maximum score Alice can get.

Example
Input
5
1 3
3 5 1 2
1 4
3 5 1 2
2 25
10 50 3 25
10 60 5 20
2 20
10 50 3 25
10 60 5 20
2 5
5 100 1 1
4 2 1 1
Output
0
3
85
50
1
Note

In the first test case, Alice solves the problem at $$$t = 3$$$. Bob hacks Alice's submission. Alice does not have any time left to fix it. Hence Alice gains $$$0$$$ points.

In the second test case, Alice solves the problem at $$$t = 3$$$. Bob hacks Alice's submission. Alice fixes her solution by $$$t = 4$$$. Hence Alice gains $$$(5-2)=3$$$ points.

The third and fourth test cases are explained above in the statemet.