Woburn Challenge 2015-16 Round 1 - Senior Division

Problem 1: Woburn Workload

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 ≤ N ≤ 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 Mi (1 ≤ Mi ≤ 106) 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, M1 < M2 < … < MN).

Furthermore, each assignment i takes Ti (1 ≤ Ti ≤ 106) 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 Ti minutes is guaranteed to be your best work, if you spend Si minutes working on assignment i, where Si ≤ Ti (spending extra time on an assignment does no good), you'll have to incur Ti − Si 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 Format

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 Mi and Ti, 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 Format

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.

All Submissions
Best Solutions


Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 17, 2015
Authors: SourSpinach, Alex

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