Шукачі скарбів#5529

Шукачі скарбів

1 секунда

256 мегабайтів

Легка

У результаті тривалих пошуків шукачі скарбів виявили величезне поле з $N$ точками, де знаходяться золоті скарби. Ватажок має карту, на якій вказані координати та кількість золота у кожному зі скарбів. Поле являє собою множину точок $(x, y)$ на прямокутній координатній площині, де всі ординати додатні. Табір шукачів скарбів розміщено вздовж осі $X$ . Координати скарбів — цілі числа.

У ватажка є такий секретний план: він почне з будь-якої точки поля з цілими координатами й вирушить до табору. Щоб не викликати підозр у інших шукачів скарбів, з кожної точки $(x, y)$ він переходитиме лише в одну з таких: $(x - 1, y - 1)$ (x-1, y-1), $(x, y - 1)$ (x, y-1) або $(x + 1, y - 1)$ (x+1, y-1). Проходячи точку зі скарбом, він непомітно забирає з неї все золото. Коли ватажок досягне осі $X$ , він зупиниться. Знайдіть максимальну кількість золота, яку він може зібрати, діючи за цим планом.

Вхідні дані

Перший рядок містить ціле число $N$ ( $3 \leq N \leq 50000$ 3 \leq N \leq 50000). Кожен з наступних $N$ рядків містить три цілі числа $x_{i}$ x_i, $y_{i}$ y_i, $c_{i}$ c_i — координати $i$ -го скарбу та кількість золота у ньому. Кожна координата $x$ задовольняє $- 1000000000 \leq x \leq 1000000000$ -1000000000 \leq x \leq 1000000000. Кожна координата $y$ задовольняє $1 \leq y \leq 1000000000$ 1 \leq y \leq 1000000000. Кількість золота у кожному скарбі — ціле число з діапазону $[1, 1 0^{9}]$ [1, 10^9].

Вихідні дані

Виведіть одне ціле число — максимальну кількість золота, яку може зібрати ватажок.

Приклади

Приклад 1