2015 Mock CCC by Alex and Timothy

Miyuki is competing in a sports event known as the Ice Pillars Break. In this event, there are ~N~ ~(2 \le N \le 100\,000)~ ice pillars placed in a line and conveniently numbered ~1 \dots N~ from left to right. Pillar ~i~ has a durability ~D_i~ ~(1 \le D_i \le 10^9)~ and a weight ~W_i~ ~(0 \le W_i \le 10^9)~ for ~i = 1 \dots N~. Each second, Miyuki can reduce the durability of any pillar by 1. When a pillar's durability becomes less than or equal to 0, it collapses and removes durability equal to its weight from each of the two pillars adjacent to it (pillars ~1~ and ~N~ only have one other pillar adjacent to them). Miyuki wants to finish with as fast a time as possible, so please help her calculate the minimum number of seconds it will take to collapse all of the pillars.

Scoring

In addition to the constraints above, the following will hold:

• For test cases worth 20% of the points, ~N \le 8~.
• For test cases worth 60% of the points, ~N \le 300~, ~D_i, W_i \le 1\,000~.

Input Specification

The first line of input will have the integer ~N~.
For the next ~N~ lines, the ~i^{th}~ of these lines will contain two space-separated integers ~D_i~ and ~W_i~.

Output Specification

Output one integer, the minimum number of seconds required to reduce the durability of all pillars to 0 or lower.

Please note that this answer may be very large and is not guaranteed to fit within a 32-bit integer.

Sample Input 1

5
5 5
7 2
8 1
2 0
1 3

Sample Output 1

14

Explanation for Sample 1

Destroy the 5th pillar, then the 1st pillar, then the 2nd pillar, and finally the 3rd pillar. At this point, the 4th pillar will already be destroyed.

Sample Input 2

3
5 6
6 4
4 0

Sample Output 2

5

Explanation for Sample 2

If you knock over the 1st pillar, you get a chain reaction which destroys all other pillars.