George has procrastinated too much on his homework assignments, and now he is running out of time to finish them all.
Each of George's assignments has a weight that it contributes to his grade and a deadline in days from today. George will need one day to finish any of the assignments and he must complete an assignment before its deadline in order to submit it (he can't complete it the day an assignment is due).
Help George figure out the order in which he should complete his assignments such that the total weight of the assignments he completes is maximized.
Input Specification
The standard input will contain 10 datasets. Each dataset begins with an integer
.
The next lines contain an integer
and a decimal
, representing an assignment that has a deadline in
days from today and a weight of
.
For the first seven cases, .
Output Specification
For each dataset, output the maximum total weight of the assignments that George can complete, rounded to 4 decimal places (George is very meticulous about his grades).
Sample Input (Two Datasets Shown)
3
1 1.0
2 1.0
3 1.0
5
1 2.0
1 1.0
3 3.0
7 10.0
3 2.0
Sample Output
3.0000
17.0000
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org
Comments