## Problem S4: Ice Pillars

Miyuki is competing in a sports event known as the Ice Pillars Break. In this event, there are N (2 ≤ N ≤ 105) ice pillars placed in a line and conveniently numbered 1..N from left to right. Pillar i has a durability Di (1 ≤ Di ≤ 109) and a weight Wi (0 ≤ Wi ≤ 109) for i = 1..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 ≤ 8.
• For test cases worth 60% of the points: N ≤ 300 and Di, Wi ≤ 1000.

### Input Format

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 Di and Wi.

### Output Format

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.

```5
5 5
7 2
8 1
2 0
1 3
```

```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.

```3
5 6
6 4
4 0
```

```5
```

### Explanation for Sample 2

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

Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 64M