Bookshelf

Chansu has N books numbered from 1 to N. Book i has thickness ti and height hi. The books must be placed on the bookshelf in increasing order of their numbers, and their order cannot be changed.

Books are placed from the bottom shelf upward. On one shelf, books are placed from left to right in increasing order. Once Chansu starts placing books on a higher shelf, he cannot go back down to place more books on a lower shelf.

The height of a shelf is the maximum height of any book on that shelf. The total height H used by the bookshelf is the sum of the heights of all shelves that contain books. The width of a shelf is the sum of the thicknesses of the books on it, and the bookshelf width L is the maximum shelf width. Ignore the thickness of the wood used to build the bookshelf.

After all books are placed, Chansu wants to minimize max(H, L). Find the minimum possible value.

The first line contains the number of books N.

Each of the next N lines contains two integers ti and hi, the thickness and height of one book, given in book-number order.

Print one integer: the minimum possible value of max(H, L), where H is the total bookshelf height and L is the bookshelf width after all books are placed.

• 1 <= N <= 100,000
• 1 <= ti, hi <= 10,000