ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Championship March'2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Queue at the Exam

Time limit: 0.5 second
Memory limit: 64 MB
A group of students are having an oral examination. At the beginning of the exam, all students simultaneously receive their questions and start preparing for the answer. Each student needs T1 minutes for the preparation and T2 minutes for the answer itself (these parameters can be different for different students). For each student, the time T3 (in minutes from the planned beginning of the exam) is given when this student has to be free because she has other things to do (for example, other exams).
During the exam, a queue of students is formed as they are getting ready to speak. If a student is ready to answer and at that time moment the professor is free, then this student starts answering immediately. If the professor is busy with another person, then the student joins the queue and starts answering when the student before her in the queue finishes her examination.
It is possible that some students won't be free when they planned to be (i.e., at the time T3). The professor is ready to cooperate and can shift the beginning of the exam to an earlier time. However, he doesn't want to come too early! You task is to write a program that will calculate the minimal period in minutes by which the exam should be shifted so that all the students will manage to complete the exam before their T3 time.


The first line contains the number of students N (1 ≤ N ≤ 40). Each of the next N lines contains the corresponding numbers T1, T2, and T3. The numbers are separated with spaces and satisfy the constraints 0 ≤ T1 ≤ T3 ≤ 600, 1 ≤ T2 ≤ 240. All the numbers T1 are distinct.


Output the nonnegative integer that is the answer to the problem. If there is no need to shift the beginning of the exam, output 0.


100 10 120
70 40 150
99 15 400
100 10 110
80 15 100
Problem Author: Anatoly Uglov
Problem Source: Fifth High School Children Programming Contest, Ekaterinburg, March 02, 2002
To submit the solution for this problem go to the Problem set: 1193. Queue at the Exam