Time Limit: 1000ms
Memory Limit: 65536kb
DescriptionGzsun, dapan and dandan often go to ZhengYang dining-room to have lunch together after the course "Parallel Computing" on Thursdays.
The course is over after 12 o'clock, and the three guys are so hungry that they want the cook process their orders as soon as possible.
The cook usually makes rational planning about the guests' menus. But today there are so many guests, he seems in a muddle and makes the three guys wait for such a long time. Gzsun suggests we help the cook to plan reasonably so that such unpleasant things would not happen again. He simplifies the problem as the following:
1. The cook gets all the menus at the same time (t=0) so he can schedule his task globally. This is reasonable because the students have their classes over at the same time.
2. Once he decides to process a menu, he will not stop until finished.
3. He is so experienced that he can estimate the time cost for every menu.
4. Each guest (not each table) orders one menu. The guests start waiting at time t=0. The goal is to make the average waiting time smallest.
Now it's your time to solve it.
InputThere are several cases. Every case begins with n(1<=n<=100), the number of guests. The next n lines each will start with a name, and followed by the time cost of his menu. The name is a string consisting of at most 20 letters or digits. The time cost is a positive integer not more than 100. The input is ended by n = 0.
OutputFor each case, print the average waiting time on a line by itself. The results are rounded to 3 digits after the decimal point.
1 guest1 10 3 gzsun 10 dapan 20 dandan 30 0