Разделяй и властвуй
Разделяй и властвуй
Мансур играет в новую компьютерную стратегическую игру. Одной из самых главных задач в таких играх является добыча ресурсов. К счастью в этой игре только один необходимый для развития ресурс - это золото, и один вспомогательный - энергия.
В этой игре существуют рудники, которые вырабатывают определенное количество золота и энергии. Все рудники находятся на одной прямой. Для того чтобы защитить собственные рудники можно построить силовое поле (отрезок на данной прямой покрывающий рудники, в том числе находящиеся в концах отрезка), которое потребляет энергию, равную своей длине.
Мансур хочет построить одно силовое поле таким образом, чтобы энергии вырабатываемой рудниками, защищенными этим полем, было достаточно для снабжения поля энергией, а золота, добываемого этими рудниками, было как можно больше.
Помогите Мансуру, напишите программу, которая будет определять, какое максимальное количество золота он может добыть с защищенных рудников.
Входные данные
В первой строке находится единственное целое число n~(1 \le n \le 10^5) — количество рудников. Далее следуют n строк, каждая содержит три целых числа, разделенных пробелами x_i, g_i, d_i~(0 \le x_i \le 10^9, 1 \le g_i \le 10^9, 1 \le d_i \le 10^9) — координаты рудника, вырабатываемое количество золота и вырабатываемое количество энергии соответственно. Все x_i различны и даны в возрастающем порядке.
Выходные данные
Выведите единственное число — максимальное количество золота, которое может добыть Мансур в игре.
Пример
4 0 5 1 1 7 2 4 4 1 7 15 1
16