George has procrastinated too much on his ~N~ homework assignments, and now he is running out of time to finish them all.
Each of George's ~N~ 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.
The standard input will contain 10 datasets. Each dataset begins with an integer ~N\,(1\leq N\leq10^6)~.
The next ~N~ lines contain an integer ~D~ and a decimal ~W\,(1\leq D\leq 10^6, 0<W\leq100)~, representing an assignment that has a deadline in ~D~ days from today and a weight of ~W~.
For the first seven cases, ~N\leq1000~.
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
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org