Consider an old cassette player,
whose only working buttons are “play” and “rewind”.
You have just one cassette, which you always keep completely rewinded.
So, when you want to listen to a particular song *s*,
you have to press the “play” button
and wait until all the songs stored before *s* finish.
Afterwards, when *s* ends,
you always rewind the cassette.

You have *n* songs.
You know that you want to listen to song *i* with absolute frequency *f*_{i}.
(For instance, if *f*_{1} = 6 and *f*_{2} = 3,
then you listen to song 1 twice as much as to song 2.)
You also know the duration *d*_{i} of every song *i*.
Assume that the cassette is long enough to store all your songs.
Your goal is to choose the order to store the songs
so as to minimize the expected time to listen to a desired song.

**Input**

Input is all natural numbers, and consists of several cases.
Every case begins with *n*,
which is followed by *n* pairs *f*_{i} *d*_{i}.
At least one of the frequencies is strictly positive.
All the durations are strictly positive.
Assume 1 ≤ *n* ≤ 10^{5}.

**Output**

For every case, print with four digits after the decimal point the optimal expected time to listen to a desired song. The input cases have no precision issues.

Public test cases

**Input**

2 6 1 6 1 2 6 1 3 1 2 6 3 6 1 2 6 3 3 1 4 3 9 0 8 1 4 4 7 1 8 100

**Output**

1.5000 1.3333 2.5000 3.0000 12.0000 100.0000

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++