407376: GYM102775 L Вишневый вопрос

После долгого отсутствия Раневская наконец-то вернулась в родное поместье. Но вместе с тёплыми воспоминаниями к ней пришли и старые долги. И вот она стоит на пороге банкротства — нужно продавать любимое поместье вместе с вишнёвым садом. Причем ровно в это время на деревьях распускаются цветы! Поэтому она хочет назначить торги на следующий день после самого бурного цветения.

Более подробно: в её саду растет N вишневых деревьев. Про каждое дерево известно: a_i — день, когда оно начинает расцветать, утром этого дня на нем появляется k_i цветков, каждое следующее утро их число увеличивается на k_i до b_i дня включительно. Далее на i-м дереве увядает k_i цветков каждый день, начиная с вечера b_i дня.

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

В первой строке входных данных находится единственное N (1 ≤ N ≤ 10⁵)  — количество деревьев. Далее в i + 1 строке находится информация об i-м дереве: числа a_i, b_i и k_i (1 ≤ a_i ≤ b_i ≤ 10⁹, 1 ≤ k_i ≤ 10⁹).

Гарантируется, что ответ помещается в 64-битный тип данных.

В единственной строке выведите число — самый первый день, в который число цветков на всех деревьях будет наибольшим.

3
1 9 1
20 24 2
35 36 5

24

Утром 9-го дня суммарное число цветков будет равно 9.

Утром 24-го дня суммарное число цветков будет равно 10.

Утром 36-го дня суммарное число цветков будет равно 10.

Максимальное число цветков на деревьях – 10, первый раз такое количество будет в 24-й день.