eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Разделяй и властвуй

Разделяй и властвуй

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Мансур играет в новую компьютерную стратегическую игру. Одной из самых главных задач в таких играх является добыча ресурсов. К счастью в этой игре только один необходимый для развития ресурс - это золото, и один вспомогательный - энергия.

В этой игре существуют рудники, которые вырабатывают определенное количество золота и энергии. Все рудники находятся на одной прямой. Для того чтобы защитить собственные рудники можно построить силовое поле (отрезок на данной прямой покрывающий рудники, в том числе находящиеся в концах отрезка), которое потребляет энергию, равную своей длине.

Мансур хочет построить одно силовое поле таким образом, чтобы энергии вырабатываемой рудниками, защищенными этим полем, было достаточно для снабжения поля энергией, а золота, добываемого этими рудниками, было как можно больше.

Помогите Мансуру, напишите программу, которая будет определять, какое максимальное количество золота он может добыть с защищенных рудников.

Входные данные

В первой строке находится единственное целое число 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 различны и даны в возрастающем порядке.

Выходные данные

Выведите единственное число — максимальное количество золота, которое может добыть Мансур в игре.

Пример

Входные данные #1
4
0 5 1
1 7 2
4 4 1
7 15 1
Выходные данные #1
16
Источник 2014 X Международная Жаутыковская Олимпиада Алматы, Казахстан, 12-18 января