Кладоискатели
В результате длительных поисков кладоискатели обнаружили огромное поле, на котором есть N точек с золотыми кладами. У предводителя есть карта, на которой помечены координаты и количество золота в каждом из кладов. Поле представляет собой множество тех точек (x, y) прямоугольной координатной плоскости, ординаты которых положительны. Лагерь кладоискателей расположен по всей оси X. Координаты точек с кладами – целые числа.
У предводителя есть такой секретный план: он подойдёт к какой-либо точке поля с целыми координатами и начнёт двигаться к лагерю. Чтобы его движение не показалось подозрительным другим кладоискателям, из каждой точки (x, y) он будет передвигаться только в точку (x-1, y-1), (x, y-1) или (x+1, y-1). Проходя точку с кладом, он будет незаметно забирать себе из него всё золото. Когда предводитель достигнет оси X, он остановится. Найдите максимальное количество золота, которое сможет присвоить предводитель кладоискателей, действуя согласно своему плану.
Входные данные
Первая строка содержит целое число N (3 ≤ N ≤ 50000). Каждая из следующих N строк содержит числа x_i, y_i, c_i – координаты i-ого клада и количество золота в нём, соответственно. Координата x каждого из кладов удовлетворяет условию -1000000000 ≤ x ≤ 1000000000. Координата y каждого из кладов удовлетворяет условию 1 ≤ y ≤ 1000000000. Количество золота в каждом из кладов – целое число в диапазоне [1, 10^9].
Выходные данные
Единственное целое число – максимальное возможное количество золота, собранного предводителем.