LAZYPROG  The lazy programmer
A new webdesign studio, called SMART (Simply Masters of ART), employs two people. The first one is a webdesigner and an executive director at the same time. The second one is a programmer. The director is so a nimble guy that the studio has already got N contracts for web site development. Each contract has a deadline d_{i}.
It is known that the programmer is lazy. Usually he does not work as fast as he could. Therefore, under normal conditions the programmer needs b_{i} of time to perform the contract number i. Fortunately, the guy is very greedy for money. If the director pays him x_{i} dollars extra, he needs only (b_{i}  a_{i}*x_{i}) of time to do his job. But this extra payment does not influence other contracts. This means that each contract should be paid separately to be done faster. The programmer is so greedy that he can do his job almost instantly if the extra payment is (b_{i}/a_{i}) dollars for the contract number i.
The director has a difficult problem to solve. He needs to organize programmer’s job and, may be, assign extra payments for some of the contracts so that all contracts are performed in time. Obviously he wishes to minimize the sum of extra payments. Help the director!
Input
First line of the input contains an integer t (1 ≤ t ≤ 45), equal to the number of testcases. Then descriptions of t testcases follow.
First line of description contains the number of contracts N (1 ≤ N ≤ 100000, integer). Each of the next N lines describes one contract and contains integer numbers a_{i}, b_{i}, d_{i} (1 ≤ a_{i}, b_{i} ≤ 10000; 1 ≤ d_{i} ≤ 1000000000) separated by spaces.
At least 90% of testcases will have 1 ≤ N ≤ 10000.
Output
For each testcase in the input your program should output one line with a single real number S. Here S is the minimum sum of money which the director needs to pay extra so that the programmer could perform all contracts in time. The number must have two digits after the decimal point.
Example
Input: 1 2 20 50 100 10 100 50 Output: 5.00
hide comments
hackher69:
20200602 11:28:27
Sample Input


pandey101299:
20191230 08:11:00
and i can't understand use of b/a when (ba*x) is given. 

pandey101299:
20191230 08:05:33
Last edit: 20200205 15:45:50 

milanjain22:
20191207 16:03:12
Results are to be rounded off and not truncated. example


huynhtuan71ti:
20190906 17:01:07
AC in one go 

lucina101:
20190118 05:51:25
Cool problem!


entergmode:
20180804 13:30:16
Please correct me if i am wrong.


arpit728:
20180512 10:05:06
Getting TLE, can anyone please tell what is wrong with my solution.


arpit728:
20180303 05:03:03
Can anyone please write explanation for the sample test case. 

Vipul Srivastava:
20170311 14:02:24
Very nice question 
Added by:  Ivan Metelsky 
Date:  20050825 
Time limit:  1.491s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  NEERC Western Subregion QF 2004 