Задача E. Эффективное чтение ≡

Условие

С тех пор как Петя поступил на филфак, его жизнь круто изменилась. Оказалось, что нужно много читать для того, чтобы успевать по всем предметам. Петя читает книги только из университетской библиотеки. Поскольку Петя — не единственный студент в университете, он не может взять все нужные ему книги в начале семестра и сдать в конце. Для каждой книги определена дата, в которую Петя должен её взять и дата, в которую Петя должен её вернуть.

Более формально, занумеруем дни учебного семестра начиная с 1. Пете для учебы необходимо N книг. Занумеруем их числами от 1 до N. Для книги с номером i известны три числа:

• L_i — номер дня, в который книгу следует взять в библиотеке;
• R_i — номер дня, в который книгу следует отдать;
• p_i — количество страниц в книге.

Будем считать, что Петя приходит в библиотеку утром, забирая и отдавая необходимые книги. Таким образом, взяв книгу в день с номером L_i, он может в тот же день начать её читать. Вместе с этим, если книгу необходимо отдать в день с номером R_i, то Петя должен успеть дочитать её в день с номером R_i − 1.

Петя хочет прочесть все необходимые ему книги. За день Петя может прочесть любое неотрицательное целое число страниц из любых имеющихся у него книг, однако хочет распределить нагрузку максимально равномерно. Найдите такое наименьшее целое P, что, читая не более P страниц в день, Петя достигнет своей цели.

В приведённом примере имеется 2 книги и 3 дня для чтения (в день номер 4 Петя приходит в библиотеку утром). В первый день Петя берёт в библиотеке книгу с номером 1 и прочитывает, например, 30 страниц из неё. Во второй день Петя берёт книгу с номером 2. Поскольку эту книгу необходимо отдать в следующий день, все её 50 страниц следует прочесть в день с номером 2. На третий день Петя относит книгу 2 в библиотеку и дочитывает оставшиеся 30 страниц первой книги. Таким образом, Петя может прочесть обе книги, читая не более 50 страниц в день. С другой стороны, ответ не может быть меньше 50, поскольку вторую книгу нужно прочесть за один день.

Рекомендуется рассмотреть частичные решения

N = 1;

N ≤ 10³;

Формат входного файла

Входной файл содержит целое число N, за которым следует N троек целых чисел L_i R_i p_i.

Формат выходного файла

Выходной файл должен содержать единственное целое число P.

Ограничения

1 ≤ N ≤ 10⁵;

1 ≤ L_i < R_i ≤ 10⁵;

1 ≤ p_i ≤ 10⁵;

Примеры тестов

2
1 4 60
2 3 50

50