Server

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 $\frac{\sum_{i\in S}A_i}{\sum_{i\in S}B_i}$ 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 \leq 100000, t \leq 100000)$ as described above. In the next $N$ lines, the $i$-th line consists of four integer $S_i$, $T_i$, $A_i$, and $B_i$ $(1 \leq S_i \leq T_i \leq t, 0 < A_i, B_i \leq 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

2017 ACM/ICPC 哈尔滨赛区网络赛——测试专用