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 T₁ minutes for the preparation and T₂ minutes for the answer itself (these parameters can be different for different students). For each student, the time T₃ (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 T₃). 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 T₃ time.

The first line contains the number of students N (1 ≤ N ≤ 40). Each of the next N lines contains the corresponding numbers T₁, T₂, and T₃. The numbers are separated with spaces and satisfy the constraints 0 ≤ T₁ ≤ T₃ ≤ 600, 1 ≤ T₂ ≤ 240. All the numbers T₁ 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.