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 reigons that they will visit. He will start from MNNIT and visit all the reigons one by one in buses. 

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

If the tempreture 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 cnditions. As the cost of products varies from reigon to reigon, the refreshment cost on avg. per member on bus in reigon i is Rs. xi. 

As Akshat wants to save money, he thinks of adding/removing buses in the begining of the trip and between reigons (they need at least one bus to pass any reigon). Assume that buses have infinite capacity and Friends can be randomly distributed on buses. Each of the bus in reigon 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 reigons in the trip and number of friends.

Next n lines contains four integers : the ith line contains ti (temp. of reigon), Ti(max. tolerable temp.), xi(Avg. refreshment cost), Ci (cost per bus).(1<=ti,Ti,xi,Ci<=10^6).

Output

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

Sample Test Case: 

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