# Filling a bookshelf (1) P34745

Statement

thehtml

Professor Oak has b books, each one with width wi and height hi, 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 hi’s, and that the goal is to maximize the sum of the wi’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 wi and hi. Assume 1 ≤ b ≤ 103 and 1 ≤ wi, hi ≤ 109. 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
22
5
13
67
63
15
```
• Information
Author