Problems
Кладоискатели
Кладоискатели
В результате длительных поисков кладоискатели обнаружили огромное поле, на котором есть \textbf{N} точек с золотыми кладами. У предводителя есть карта, на которой помечены координаты и количество золота в каждом из кладов. Поле представляет собой множество тех точек (\textbf{x}, \textbf{y}) прямоугольной координатной плоскости, ординаты которых положительны. Лагерь кладоискателей расположен по всей оси \textbf{X}. Координаты точек с кладами -- целые числа.
У предводителя есть такой секретный план: он подойдёт к какой-либо точке поля с целыми координатами и начнёт двигаться к лагерю. Чтобы его движение не показалось подозрительным другим кладоискателям, из каждой точки (\textbf{x}, \textbf{y}) он будет передвигаться только в точку (\textbf{x-1}, \textbf{y-1}), (\textbf{x}, \textbf{y-1}) или (\textbf{x+1}, \textbf{y-1}). Проходя точку с кладом, он будет незаметно забирать себе из него всё золото. Когда предводитель достигнет оси \textbf{X}, он остановится. Найдите максимальное количество золота, которое сможет присвоить предводитель кладоискателей, действуя согласно своему плану.
\InputFile
Первая строка содержит целое число \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{50000}). Каждая из следующих \textbf{N} строк содержит числа \textbf{x_i}, \textbf{y_i}, \textbf{c_i} -- координаты \textbf{i}-ого клада и количество золота в нём, соответственно. Координата \textbf{x} каждого из кладов удовлетворяет условию \textbf{-1000000000} ≤ \textbf{x} ≤ \textbf{1000000000}. Координата \textbf{y} каждого из кладов удовлетворяет условию \textbf{1} ≤ \textbf{y} ≤ \textbf{1000000000}. Количество золота в каждом из кладов -- целое число в диапазоне \[\textbf{1}, \textbf{10^9}\].
\OutputFile
Единственное целое число -- максимальное возможное количество золота, собранного предводителем.
Input example #1
5 0 5 2 2 4 3 -1 3 2 0 2 1 1 1 3
Output example #1
8