時間制限:5000ミリ秒
メモリ制限:65536KB
問題
WebデザインのスタジオであるSMART(Simply Masters of ART)は新たに2人の社員を雇った。最初の一人はWebデザイナーとエグゼクティブディレクターを同時にこなし、もう一人はプログラマである。ディレクターはとても仕事が早い人で、もう N 個のWebサイト製作の契約を結んでいた。i番目の契約の納期は di である。
が、プログラマは怠け者であった。彼は自分の全力を出して仕事をしない。彼のいつもの状態だと i 番目の仕事を終えるのに bi の時間がかかる。幸運なことに、プログラマはとてもお金が大好きで貪欲な男だった。彼はディレクターから xi ドルの余計な報酬をもらうと (bi - ai*xi) 時間で i 番目の仕事を終えてしまう。各々の仕事について、それを早く終わらせたいならば別々に余計な報酬を支払わねばならない。そのプログラマは非常にお金に貪欲であったため、もし i 番目の仕事についての余計な報酬の支払いが (bi / ai) ドルになると、ほぼ時間0でその仕事を終えてしまう。
さて、ここでディレクターは難問に直面した。彼はプログラマの仕事順を決めなければならず、またおそらく、全ての契約を納期に間に合わせるためにいくらか余計な報酬を支払ってやらねばならない。当たり前だが、ディレクターは余計な報酬の額をできるだけ少なくしたいと思っている。彼を助けてやってほしい！
入力
入力の1行目には契約の個数を表す整数 N (1 ≦ N ≦ 100,000) が書かれている。続く N 行はそれぞれ1つの契約を表す。1つの契約は3つの整数 ai, bi, di (1 ≦ ai, bi ≦ 10,000; 1 ≦ di ≦ 1,000,000,000) が空白区切で書かれている。
出力
出力は1行からなり、この1行には実数 S を出力する。ここで S は全ての契約を納期に間に合わせるためにディレクターがプログラマに支払わねばならない余計な報酬の合計の最小値である。Sは小数点以下第2位まで出力すること。
入力の例
2 20 50 100 10 100 50
出力の例
5.00
出典
Northeastern Europe 2004, Western Subregion