Woburn Challenge 2015-16 Round 1 - Senior Division

Welcome to the first Woburn Challenge in over a decade! We hope you find these contests fun and challenging.

Let's start by getting to know Woburn a little more. The motto of Woburn Collegiate Institute is Studium Eruditionis Crescat, or Let the Zeal for Learning Flourish. Clearly, Woburn values academic excellency, so it's no surprise that students often receive a hefty workload. There are also many extracurricular opportunities available to students, including Woburn Music, drama, and of course, the Programming Enrichment Group. Members of PEG meet Wednesdays and Fridays after school to study advanced computer science concepts, and are often assigned a fair amount of programming homework. Not only has PEG made students superb at programming, they've made students love programming. In fact, PEG students are often so hooked onto their programming homework that they forget about actual homework and become swamped with upcoming deadlines!

Being the natural problem-solvers they are, PEG students have realized that programming is once again the solution. They've decided to write a program to help them handle the workload of Woburn's courses, and they've asked you for help! Specifically, there are ~N~ ~(1 \le N \le 100)~ homework assignments that they would like to feed to your program. Each assignment is labeled with a unique integer from ~1~ to ~N~, and will be given to your program in order. Each assignment ~i~ is due ~M_i~ ~(1 \le M_i \le 10^6)~ minutes from now. Any given assignment can only be worked on up until the time at which it's due. The assignments will be given to your program in strictly increasing order of due date (in other words, ~M_1 < M_2 < \ldots < M_N~).

Furthermore, each assignment ~i~ takes ~T_i~ ~(1 \le T_i \le 10^6)~ minutes to fully complete. The amount of marks you get on an assignment is obviously proportional to the amount of time you spend working on it. Since spending all ~T_i~ minutes is guaranteed to be your best work, if you spend ~S_i~ minutes working on assignment ~i~, where ~S_i \le T_i~ (spending extra time on an assignment does no good), you'll have to incur ~T_i - S_i~ penalty marks. You can only work on one homework assignment at a time, but you can switch from one assignment to another at any point in time. Time is tight, so you might not be able to fully complete every assignment. The goal of the program is to help the user allocate their precious time amongst the assignments. Your program must answer the question: what's the minimum total number of penalty marks that can be incurred across all of the assignments?

Input Specification

The first line of input will contain a single integer ~N~, representing the number of assignments to follow.
~N~ lines will follow, with the ~i~-th of these lines containing two space-separated integers ~M_i~ and ~T_i~, respectively representing the number of minutes from now at which assignment ~i~ is due and the number of minutes it takes to complete assignment ~i~.

Output Specification

Output a single integer representing the minimum total penalty marks that can be incurred across all of the assignments, if your program schedules the assignments optimally.

Sample Input

4
40 40
80 60
120 30
130 80

Sample Output

80

Explanation

There are four assignments, respectively due ~40~, ~80~, ~120~, and ~130~ minutes from now and respectively requiring ~40~, ~60~, ~30~, and ~80~ minutes to complete. One way to optimally tackle the assignments is as follows:

• Immediate start working on assignment ~1~. You'll be done just in the nick of time and incur no penalty marks.
• Right after you hand in assignment ~1~ (at ~40~ minutes in), start working on assignment ~2~. Unfortunately, you'll only have ~40~ minutes to work on the assignment, and so you'll have to incur ~60 - 40 = 20~ penalty marks.
• Right after you hand in assignment ~2~ (at ~80~ minutes in), start working on assignment ~4~. You'll be able to get ~50~ minutes of work on it before the due date (at ~130~ minutes in). You'll have to incur ~80-50 = 30~ penalty marks.
• Unfortunately, there was no time at all to tackle assignment ~3~, so you'll have to accept a zero and incur the full ~30~ penalty marks.

In total, there are ~20 + 30 + 30 = 80~ penalty marks incurred. There may be other ways to tackle the assignments, but it turns out that they will all incur ~80~ penalty marks or more.