Akshat aka Singham, watches a lot of TV Series. Today he finished Castle, he is bored now and is planning for a trip with friends. He has N friends. As you all know Singham is very cautious and wants to save every penny he can. He has identified few regions that they will visit. He will start from MNNIT and visit all the regions one by one in buses.

Assume that all regions are connect by a single road running through these regions. Each region has a temperature ti units, if a bus is travelling through ith region and has k people in it then the temperature of the bus ti+k units.

If the temperature of the bus exceeds Ti units, then each of the member on the bus ask for refreshment in the form of ice -cream, drinks due to uncomfortable conditions. As the cost of products varies from region to region, the refreshment cost on average per member on bus in region i is Rs. xi.

As Akshat wants to save money, he thinks of adding/removing buses in the beginning of the trip and between regions (they need at least one bus to pass any region). Assume that buses have infinite capacity and friends can be randomly distributed on buses. Each of the bus in region i cost Rs. Ci.

You have to help Akshat find the minimum cost needed to organize the trip.

Input

First Line contains one integer tc, representing the number of test cases, then tc test cases follow.

Each test cases starts with two integer on first line n and m (1 <= n <= 10^5; 1 <= m <= 10^6) -- the number of regions in the trip and number of friends.

Next n lines contains four integers: the ith line contains ti (temperature of region), Ti (maximum tolerable temperature), xi (Average refreshment cost), Ci (cost per bus).(1 <= ti, Ti, xi, Ci <= 10^6).

Output

Print one integer, minimum cost needed to organize to trip. (Warning: Output may not be in the range of integer)

Example

Input:
2
2 10
30 35 1 100
20 35 10 10
3 100
10 30 1000 1
5 10 1000 3
10 40 1000 100000

Output:
120
200065