Filling a bookshelf (1) P34745

Professor Oak has $b$ books, each one with width $w_i$ and height $h_i$, and he wants to use them to fill a bookshelf as much as possible. For aesthetic reasons, Prof. Oak wants the second book (if any) to be shorter than the first book, the third book to be taller than the second book, …, and the last book to be taller than the penultimate book, so that the bookshelf has sort of a zigzag look: down, up, down, up, …, down and up. 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.

Please write a program to help Prof. Oak. Take into account that, when filling the bookshelf, the relative order of the books in the input cannot be changed.

Input

Input consists of several cases. Each case begins with $b$, followed by $b$ pairs with $w_i$ and $h_i$. Assume $1 \le b \le 10^3$ and $1 \le w_i, h_i \le 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.