e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

Озеро Елеонори

Відомий гурт "Озеро Елеонори" проводить концерт на координатній прямій. Відомо, що в країні, де вони проводять концерт, є $n$ людей. $i$-та людина живе на координаті $x_i$, має швидкість одна умовна одиниця за $w_i$ секунд, а також буде чути концерт, якщо він буде проходити на відстані не більше $d_i$ умовних одиниць від місцеперебування людини. Гурту О.Е. потрібно вибрати цілочисельну точку, де вони проведуть концерт. Всі люди, які здому не будуть чути їхній концерт, будуть вимушені рухатися до місця проведення концерту доти, доки не почують його (тобто, на відстані $d_i$). Допоможіть гурту знайти таку точку, яка мінімізує сумарний час усіх людей на те, щоб дібратися до точки, де вони будуть чути концерт. Проте виведіть не саму точку, а мінімально можливу суму. \InputFile Перший рядок містить одне ціле число $n$ ($1 \leq n \leq 200\,000$). Кожен з наступних $n$ рядків містить три цілі числа $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$). \OutputFile Виведіть одне ціле число~--- відповідь на задачу. \Scoring \begin{enumerate} \item ($28$ балів): $n, x_i, d_i \leq 2\,000$; \item ($57$ балів): $x_i, d_i \leq 10^6$; \item ($15$ балів): без додаткових обмежень. \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
1
0 1000 0
Output example #1
0
Input example #2
2
10 4 3
20 4 2
Output example #2
20
Input example #3
3
6 8 3
1 4 1
14 5 2
Output example #3
43
Author Anton Tsypko