{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eA new web-design studio, called \u003ci\u003eSMART\u003c/i\u003e (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 \u003cb\u003eN\u003c/b\u003e contracts for web site development. Each contract has a deadline \u003cb\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\u003c/p\u003e\u003cp\u003eIt 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 \u003cb\u003ei\u003c/b\u003e. Fortunately, the guy is very greedy for money. If the director pays him \u003cb\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e dollars extra, he needs only (\u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e − \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003cb\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e) of time to do his job. But this extra payment does not influent other contract. It 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 (\u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ⁄ \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e) dollars for the contract number \u003cb\u003ei\u003c/b\u003e.\u003c/p\u003e\u003cp\u003eThe 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!\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe first line of the input contains the number of contracts \u003cb\u003eN\u003c/b\u003e (1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 100 000, integer). Each of the next N lines describes one contract and contains integer numbers \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e (1 ≤ \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ 10 000; 1 ≤ \u003cb\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ 1 000 000 000) separated by spaces.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output needs to contain a single real number \u003cb\u003eS\u003c/b\u003e in the only line of file. \u003cb\u003eS\u003c/b\u003e 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.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n20 50 100\r\n10 100 50\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5.00\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}