OPCTRIP - The Trip

no tags 

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

hide comments
Shubham Gupta: 2015-11-25 23:19:57

Take your time to understand this question. Do consider the case in which you've to divide the friends in unequal parts.
#case for eg:
1
1 51
10 15 1000 10
output: 110

ADITYA PRAKASH: 2015-03-05 19:09:43

any advice regarding tle

Vipul Pandey: 2014-01-15 15:42:58

took me 30 minutes to understand the question.

JordanBelfort: 2014-01-02 22:26:17

once u understand the question its too easy..:)

RIVU DAS: 2013-12-06 19:21:49

My half century!!! :)

cenation: 2013-01-02 17:35:53

can anybody explain the second case please

Sameer Goyal: 2012-10-23 14:06:30

The ice cream is for each of the person in a bus if the bus' temperature exceeds the tolerable temperature.

david_8k: 2012-10-06 12:59:07

I still don't understand what the... is the ice cream for... Please, be more clear in the problem, also you have some grammatical errors on your statement. I read the problem more than three times and still don't understand what is the utility of the ice-cream


Added by:! include(L.ppt)
Date:2012-09-23
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MNNIT OPC 21-09-2012