Realizing that the cricket trading market is bustling, many people have changed their lives by raising and trading crickets. Tahp decides to join in to make a profit.

Tahp has invested in a cricket cage with a capacity of ~l~ crickets and wants to use it to get rich. Tahp plans to invest for ~n~ days. Initially, Tahp does not own any crickets, and by the end of day ~n~, Tahp also wants to own no crickets to focus on investing in other areas. In the next ~n~ days, Tahp will go to the market to trade crickets.

On the ~i~-th day, there are ~a_i~ crickets available for sale at a price of ~s_i~ (Vietnamese) dong per cricket. At the same time, the market also buys crickets at a price of ~b_i~ dong per cricket and only buys up to ~c_i~ crickets. Tahp can choose to buy, or sell crickets, or do nothing. However, at the end of each day, for each cricket raised, Tahp needs to spend an additional ~k~ dong to buy food for it. In addition, for all days, ~b_i \le s_i~.

Assuming Tahp always has enough money to buy more crickets and buy food, help Tahp calculate the maximum profit possible after ~n~ days.

Input

Each test may contain multiple datasets. The first line contains an integer ~t~ (~1 \le t \le 100~) — the number of datasets, followed by ~t~ groups of lines with the same structure:

• The first line contains three integers ~n~, ~l~, ~k~ (~1 \le n \le 10^5~, ~1 \le l \le 10^{12}~, ~1 \le k \le 2 \cdot 10^6~) — respectively, the number of days Tahp wants to invest, the capacity of the cricket cage, and the daily cost of buying food for each cricket;

• The ~i~-th line in the next ~n~ lines contains four integers ~a_i~, ~s_i~, ~c_i~, ~b_i~ (~1 \le a_i, s_i, c_i, b_i \le 2 \cdot 10^6~; ~b_i \le s_i~) — respectively, the number of crickets available for sale, the selling price per cricket, the maximum number of crickets that can be bought, and the buying price per cricket at the market on the ~i~-th day.

Two consecutive numbers on a line are separated by a space. The data ensures that the sum of ~n~ in all datasets does not exceed ~5 \cdot 10^5~.

Output

For each dataset, print the maximum profit on one line.

Scoring

• Subtask 1 (~750~ points): ~l \le 10~.

• Subtask 2 (~1500~ points): ~l = 10^{12}~.

• Subtask 3 (~750~ points): no additional constraints.

If you solve this problem, you will receive ~3000~ points.

Sample Input 1

2
3 4 1
2 4 2 1
3 5 1 4
1 10 3 9
2 7 2
8 7 10 1
3 9 3 8

Sample Output 1

9
0

Notes

In the first dataset, Tahp invests for ~n = 3~ days, the cricket cage has a capacity of ~l = 4~ crickets, and the daily cost of buying food for each cricket is ~k = 1~ dong. One way to maximize profit is:

• On the first day, there are ~a_1 = 2~ crickets available for sale at a price of ~s_1 = 4~ dong per cricket, and the market buys up to ~c_1 = 2~ crickets at a price of ~b_1 = 1~ dong per cricket. Tahp buys ~2~ more crickets for a total of ~2 \times 4 = 8~ dong. At the end of the day, Tahp is raising a total of ~2~ crickets and needs to spend ~2 \times 1 = 2~ dong to buy food for them.

• On the second day, there are ~a_2 = 3~ crickets available for sale at a price of ~s_2 = 5~ dong per cricket, and the market buys up to ~c_2 = 1~ cricket at a price of ~b_2 = 4~ dong per cricket. Tahp buys ~1~ more cricket for a total of ~1 \times 5 = 5~ dong. At the end of the day, Tahp is raising a total of ~3~ crickets and needs to spend ~3 \times 1 = 3~ dong to buy food for them.

• On the third day, there is ~a_3 = 1~ cricket available for sale at a price of ~s_2 = 10~ dong per cricket, and the market buys up to ~c_3 = 3~ crickets at a price of ~b_3 = 9~ dong per cricket. Tahp sells ~3~ crickets for a total of ~3 \times 9 = 27~ dong. At the end of the day, Tahp is not raising any crickets, so there is no need to buy food for them.

The total profit earned is: ~(-8) + (-2) + (-5) + (-3) + 27 = 9~ dong.