Pero is a manager of a famous bar in Skopje. During the World Cup, he wants to own a TV set, so the visitors of his bar can enjoy great football games. His goal, of course, is to make as much money as possible during the World Cup. The plan is as follows:

1. Pero's bar will own at most one TV set at a time. A TV set can be bought if the bar has at least as much money as the price of the set. Initially, at the start of the World Cup, Pero's bar has S dollars.

2. During the World Cup, Pero can buy and sell TV sets. For each TV set (which differ in display size, image quality, resolution, etc.), Pero knows the exact price Pi of the TV set, the day Ai that set can be purchased, the price Ri for which that set can be resold on the market later, and how much money Mi that set will produce each day (while Pero's bar owns it).

3. If Pero decides to purchase a TV set, he must buy it on the exact same day Ai that it becomes available, or otherwise someone else will buy it and it will become unavailable. If Pero buys a TV set on day Ai, his bar will receive it and can start using it on day Ai+1. If Pero decides to sell a TV set, he cannot use it on the day that he sells it. However, if Pero sells a TV set, he may use the money he earned by selling it right away (for example, to buy a new TV set on the same day).

After the World Cup, Pero will sell any TV set that he owns. What is the maximum amount of money that Pero's bar can have when the World Cup ends?

Input

The first line of input contains one positive integer T (1 <= T <= 15), the number of test cases.

Each test case starts with a line containing three numbers N (1 <= N <= 30 000), S (1 <= S <= 1 000 000 000), and E (1 <= E <= 1 000 000 000), the number of available TV sets (N), the initial amount of money (S), and the duration of the World Cup (E).

Each of the next N lines contains four numbers Pi, Ri (1 <= Ri < Pi <= 1 000 000 000), Mi (1 <= Mi <= 1 000 000 000) and Ai (1 <= Ai <= E), which describe the TV sets. View the task statement for description of what Pi, Ri, Mi and Ai mean.

Output

For each test case, on a separate line, output the maximum amount of money the bar can possibly have at the end of day E + 1.

Constraints

Time limit: 7 seconds
Memory limit: 64 megabytes

Examples

input
1
3 500 30
300 200 90 2
600 400 200 10
900 100 30 25

output
4830

Explanation for test case 1: On day 2, Pero can buy the first TV set (for price Pi=300). This TV set will make profit starting at day 3. On day 10, Pero can sell the TV set (for price Ri=200), and buy the second TV set (for price Pi=600). This TV set can be used until the end of the World Cup, and then sold on day 31 (E+1).

During the World Cup, the bar will earn a total of 7*90 (from using the first TV set - day 3 to day 9) + 20*200 (from using the second TV set - day 11 to day 30). Pero's bar will spend 300 + 600 dollars to buy the TV sets, and earn 200+400 dollars from reselling them. Before the World cup starts, Pero's bar has S=500 dollars.

On the end of day 31, Pero's bar will have exactly 500 + (7*90) + (20*200) - 900 + 600 = 4830 dollars.