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 ≤ b ≤ 10³ and 1 ≤ w_i, h_i ≤ 10⁹. 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.