Alice and Bob are working on a new assignment. In this project, they need to access some information on a website and monitor this web site for consistent t days. In others words, in each day, there must be at least one server in work. Luckily, they can rent some servers in the lab. According to the schedule, there are totally N servers being available. The i-th server can be used from the S_i-th day to the T_i-th day. However, using the i-th server require A_i dollars. After a long time of persuasion, the administrator of the machine room agree to give Alice and Bob discount. Each server is assigned with a discount number B_i. If the set of servers they want to use is S,  they need to pay  dollars. As Alice and Bob are preparing the programs on the servers, they want your help to find a way to minimize the cost of servers.

The first line is the number of test cases. For each test case, the first contains two positive integers N and t (N ≤ 100000, t ≤ 100000) as described above. In the next N lines, the i-th line consists of four integer Si, Ti, Ai, and Bi (1 ≤ Si ≤ Ti ≤ t, 0 < Ai, Bi ≤ 1000).

For each test case, output an float-point number with three decimal places donating the minimum cost Alice and Bob need to pay. It is guaranteed that there is at least one feasible way to rent servers.

1
4 5
1 3 28 1
4 5 22 1
3 5 34 1
1 2 26 1

25.000