PEG Judge - Mock CCC15S4

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⁵) ice pillars placed in a line and conveniently numbered 1..N from left to right. Pillar i has a durability D_i (1 ≤ D_i ≤ 10⁹) and a weight W_i (0 ≤ W_i ≤ 10⁹) 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_i ≤ 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 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

Sample Output 1

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.