Шукачі скарбів
У результаті тривалих пошуків шукачі скарбів виявили величезное поле, на якому є 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].
Вихідні дані
Єдине ціле число – максимально можлива кількість золота, зібраного ватажком.