MCAMP  Mining Camps
Mansur plays the new computer strategic game. The main task in such games is mining resources.
Fortunately in this game only one resource is necessary for development — the gold, and also there is one supplementary resource type — energy.
In this game there are mining camps, which provide certain amount of gold and energy. Аll camps are located along the straight line.
To protect the mining camps one can build a forcefield (a closed line contiguos segment containing mining camps) , which needs energy amount equal to it’s length.
( if forcefield start camp is located at X1 and its end camp is at X2 energy needed for the whole forcefield is X1X2 )
Mansur wants to build one forcefield in such way, that energy of protected mining camps is enough for the forcefield, and amount of gold provided by these mining camps is maximal possible.
Write a program to help Mansur find the maximal amount of gold which he can obtain from protected mining camps.
Input
First line of the input file contains one integer N — number of mining camps.
N<=10^5
Following N lines contain:
three space separated integers xi, gi, di, 0 <= xi <= 10^9, 1 <= gi <= 10^9, 1 <= di <= 10^9: mine coordinates,amount of gold and energy provided by the mine. All xi are different and given in increasing order.
Output
Output only one number — maximal amount of gold which Mansur can mine.Input: 4
0 5 1
1 7 2
4 4 1
7 15 1
Output: 16
The Forcefield is camps [1,3] energy is 1+2+1=4 >= 40 so answer is 5+4+7=16
hide comments
pbd:
20160223 16:00:17
@BartĀ³omiej Najdecki. Thanks for the test case. 

BartĀ³omiej Najdecki:
20160103 16:28:35
Helpful test:


Vineet Setia:
20150618 04:08:24
Mansur will get energy when he reaches that mining camp..right ? 

Vikneshwar E:
20150105 17:29:36
@Vignesh : It is given that all Xi are different. 

Vignesh Manoharan:
20140710 06:15:57
can X1=X2? like when di are too small compared to difference in xi, in which case camp at x1=x2 is inside forcefield 
Added by:  Se7s 
Date:  20140429 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  APIO 2014 Training Session 