Озеро Елеонори#10490
Відомий гурт "Озеро Елеонори" проводить концерт на координатній прямій.
Відомо, що в країні, де вони проводять концерт, є людей. -та людина живе на координаті x_i, має швидкість одна умовна одиниця за w_i секунд, а також буде чути концерт, якщо він буде проходити на відстані не більше d_i умовних одиниць від місцеперебування людини.
Гурту О.Е. потрібно вибрати цілочисельну точку, де вони проведуть концерт. Всі люди, які з дому не будуть чути їхній концерт, будуть вимушені рухатися до місця проведення концерту доти, доки не почують його (тобто, на відстані d_i).
Допоможіть гурту знайти таку точку, яка мінімізує сумарний час усіх людей на те, щоб дібратися до точки, де вони будуть чути концерт. Проте виведіть не саму точку, а мінімально можливу суму.
Перший рядок містить одне ціле число (1 \leq n \leq 200\,000).
Кожен з наступних рядків містить три цілі числа x_i, w_i, d_i (0 \leq x_i \leq 10^9, 1 \leq w_i \leq 1\,000, 0 \leq d_i \leq 10^9).
Виведіть одне ціле число — мінімально можливу суму часу.
Приклад 1
Приклад 2
Приклад 3
( балів): n, x_i, d_i \leq 2\,000;
( балів): x_i, d_i \leq 10^6;
( балів): без додаткових обмежень.