## LAZYPROG - The lazy programmer

no tags

A new web-design studio, called SMART (Simply Masters of ART), employs two people. The first one is a web-designer 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 di.

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 bi of time to perform the contract number i. Fortunately, the guy is very greedy for money. If the director pays him xi dollars extra, he needs only (bi - ai*xi) 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 (bi/ai) 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 (1t45), equal to the number of testcases. Then descriptions of t testcases follow.

First line of description contains the number of contracts N (1N100000, integer). Each of the next N lines describes one contract and contains integer numbers ai, bi, di (1ai, bi10000; 1di1000000000) separated by spaces.

At least 90% of testcases will have 1N10000.

### 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
 < Previous 1 2 Next > lucina101: 2019-01-18 05:51:25 Cool problem! entergmode: 2018-08-04 13:30:16 Please correct me if i am wrong. For anyone who spends hours to try to understand the problem like me, d is in the order of time, b is just the duration. For the example above, 20 50 100 # need 50 units of time, deadline at the 100th unit of time 10 100 50 # need 100 units of time, deadline at the 50th unit of time arpit728: 2018-05-12 10:05:06 Getting TLE, can anyone please tell what is wrong with my solution. https://pastebin.com/*********************please see notes below******** Last edit: 2018-05-12 12:18:18 arpit728: 2018-03-03 05:03:03 Can anyone please write explanation for the sample test case. Vipul Srivastava: 2017-03-11 14:02:24 Very nice question Amit Jaiswal: 2015-07-06 11:24:25 Thnx for d hint ravi kiran..yup priority queue works.. :-) Zombies: 2013-06-25 07:35:57 I m still getting WA .Please check admin.. Here is my solution http://ideone.com/*********************please see notes below******** Edit : Got the Problem (final printf with "%Lg" was not working but with "%Lf" did the job ) :D :D Last edit: 2018-05-12 12:18:36 Shubham.IIITM: 2012-07-03 12:36:27 gettng TLE... http://ideone.com/*********************please see notes below******** pls help :( Last edit: 2018-05-12 12:18:56 Cena: 2011-12-24 12:48:04 plz another test case this one is so trivial :/ Ravi Kiran: 2010-05-24 16:08:00 Phew Tough Problem!!Not as easy as it seems. Comments after solving: 1.)I got ac using only double for arithmetic wherever decimal was required. 2.)I used a priority_queue during processing. Hope this helps. :-)

 Added by: Ivan Metelsky Date: 2005-08-25 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