The statement of this problem is almost identical to the
problem : “”,
with two exceptions:
Now, when filling the bookshelf,
the relative order of the books in the input can be changed.
And *b* can be as large as 10^{5}.

I.e., the problem is:
Given *b* books, each one with width *w*_{i} and height *h*_{i},
use them to fill a bookshelf as much as possible.
The second book (if any) must be shorter than the first book,
the third book must be taller than the second book, …,
and the last book must be taller than the penultimate book.
Note that “short” and “tall” refer to the *h*_{i}’s,
and that the goal is to maximize the sum of the *w*_{i}’s of the chosen books.

**Input**

Input consists of several cases.
Each case begins with *b*,
followed by *b* pairs with *w*_{i} and *h*_{i}.
Assume 1 ≤ *b* ≤ 10^{5}
and 1 ≤ *w*_{i}, *h*_{i} ≤ 10^{9}.
A special case with *b* = 0 marks the end of input.

**Output**

For every case, print the maximum possible sum of the widths of the chosen books.

Public test cases

**Input**

3 900000000 8 700000000 4 800000000 6 2 2 8 3 6 4 8 2 9 3 6 1 7 4 2 5 7 4 7 4 4 20 6 10 3 20 8 10 6 15 3 11 1 12 3 10 2 14 2 15 3 6 15 3 11 1 12 3 10 2 14 3 15 3 6 11 1 15 2 12 2 10 3 14 2 15 2 0

**Output**

2400000000 3 24 5 15 67 65 41

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Novè Concurs de Programació de la UPC - Semifinal
- Date
- 2011-06-29