Озеро Элеоноры

Известная группа "Озеро Элеоноры" проводит концерт на координатной прямой.

В стране, где они выступают, проживает $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$ баллов): без дополнительных ограничений.