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*_{1} minutes for the preparation and *T*_{2} minutes for the answer itself (these parameters can be different for different students). For each student, the time *T*_{3} (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*_{3}). 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*_{3} time.

### Input

The first line contains the number of students *N* (1 ≤ *N* ≤ 40). Each of the next *N* lines contains the corresponding numbers *T*_{1}, *T*_{2}, and *T*_{3}. The numbers are separated with spaces and satisfy the constraints 0 ≤ *T*_{1} ≤ *T*_{3} ≤ 600, 1 ≤ *T*_{2} ≤ 240.
All the numbers *T*_{1} are distinct.

### Output

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.

### Samples

input | output |
---|

3
100 10 120
70 40 150
99 15 400 | 15 |

2
100 10 110
80 15 100 | 0 |

**Problem Author: **Anatoly Uglov

**Problem Source: **Fifth High School Children Programming Contest, Ekaterinburg, March 02, 2002