### 2015 Mock CCC by Alex and Timothy

## 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` ≤ 10^{5}) ice pillars placed in a line and conveniently numbered 1..`N` from left to right. Pillar `i` has a durability `D _{i}` (1 ≤

`D`≤ 10

_{i}^{9}) and a weight

`W`(0 ≤

_{i}`W`≤ 10

_{i}^{9}) 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`D`,_{i}`W`≤ 1000._{i}

### 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 `D _{i}` and

`W`.

_{i}### 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.

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

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 64M

**Added:** Feb 18, 2015

**Author:** FatalEagle

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...