ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1193. Очередь на зачёт

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
В студенческой группе проходит устный зачёт. В момент начала зачёта каждый студент получает от преподавателя вопрос и начинает готовиться к ответу. Для подготовки ответа студенту требуется T1 минут, а для самого ответа — T2 минут (эти параметры могут быть разными для разных студентов). Также для каждого студента известно время T3 (в минутах от запланированного времени начала зачёта), не позднее которого он должен освободиться, так как у него есть другие важные дела (например, зачёты по другим предметам).
В процессе зачёта формируется очередь по мере того, как студенты заканчивают подготовку. Если в текущий момент никто не отвечает, то подготовившийся студент немедленно начинает ответ, иначе встает в конец очереди и начинает отвечать сразу после окончания ответа того студента, который стоит в очереди перед ним.
Может так случиться, что некоторые студенты не успеют по своим делам (то есть закончат ответ позднее своего времени T3). Преподаватель готов пойти им навстречу и начать принимать зачёт пораньше. Однако приходить в университет слишком рано ему тоже не хочется! Напишите программу, которая помогла бы преподавателю и студентам: эта программа должна определить минимальное время (в минутах), на которое надо сдвинуть начало зачёта, чтобы все студенты успели по своим делам.

Исходные данные

В первой строке содержится число N — количество студентов (1 ≤ N ≤ 40) Далее следуют N строк, содержащих информацию о каждом студенте — три числа T1, T2, T3. Эти числа отделены одно от другого пробелом и удовлетворяют неравенствам 0 ≤ T1 ≤ T3 ≤ 600, 1 ≤ T2 ≤ 240. Все числа T1 попарно различны.

Результат

В единственной строке должно быть записано неотрицательное целое число, являющееся ответом на вопрос задачи. Если все студенты и так успевают по своим делам, выведите число 0.

Примеры

исходные данныерезультат
3
100 10 120
70 40 150
99 15 400
15
2
100 10 110
80 15 100
0
Автор задачи: Анатолий Углов
Источник задачи: V командное первенство школьников по программированию (2 марта 2002)