Відомий гурт "Озеро Елеонори" проводить концерт на координатній прямій. Відомо, що в країні, де вони проводять концерт, є $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}