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

Відомий гурт "Озеро Елеонори" проводить концерт на координатній прямій.

Відомо, що в країні, де вони проводять концерт, є $n$ людей. $i$-та людина живе на координаті $x_i$, має швидкість одна умовна одиниця за $w_i$ секунд, а також буде чути концерт, якщо він буде проходити на відстані не більше $d_i$ умовних одиниць від місцеперебування людини.

Гурту О.Е. потрібно вибрати цілочисельну точку, де вони проведуть концерт. Всі люди, які здому не будуть чути їхній концерт, будуть вимушені рухатися до місця проведення концерту доти, доки не почують його (тобто, на відстані $d_i$).

Допоможіть гурту знайти таку точку, яка мінімізує сумарний час усіх людей на те, щоб дібратися до точки, де вони будуть чути концерт. Проте виведіть не саму точку, а мінімально можливу суму.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 200000$).

Кожен з наступних $n$ рядків містить три цілі числа $x_i$, $w_i$, $d_i$ ($0\le x_i\le 10^9$, $1\le w_i\le 1000$, $0\le d_i\le 10^9$).

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Оцінювання

1. ($28$ балів): $n,x_i,d_i\le 2000$;

2. ($57$ балів): $x_i,d_i\le 10^6$;

3. ($15$ балів): без додаткових обмежень.