Filling a bookshelf (1) P34745


Statement
 

pdf   zip

html

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
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Semifinal
    Date
    2011-06-29