F. Cosmic timeline
time limit per test
1.5 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

The little mascot of the Shitalian mafia, Mafianca, is participating in her school's science fair. Her team must build a timeline with interesting events of the history of the universe.

Mafianca has been researching on the internet and managed to hack a NASA subdomain that has a list of N interesting cosmic events. The i-th event has the date Di and an interest value of Vi given by the scientists of NASA.

Mafianca wanted to use all events in the list, but she soon discovered they are not ordered by date. Also, the events are presented in a special manner and she can't change their order. She must choose some events to use, maximising the sum of their interest values. Her only restriction is that in her final timeline the events are not too distant time wise from each other.

Mafianca defined, for every event i, a value Ti. This value is the tolerance of the difference between the ages of this event and the previous event in the timeline. In other words, in case the event X shows up in the timeline, and the event immediately before is Y, DX - DY ≤ TX must hold true. Any event can be chosen as the starting one.

Help Mafianca build the best list possible.

Input

Input begins with an integer, n (1 ≤ n ≤ 105), the number of events. n line sfollow, each with three integers: Di (1 ≤ Di ≤ 1018), Vi (0 ≤ Vi ≤ 105) and Ti (1 ≤ Ti ≤ 106), representing the date, interest value and tolerance of the i-th event.

Output

Print the interest value of the best list Mafianca can build.

Examples
Input
3
1 2 1
3 1 1
2 2 3
Output
4
Input
3
1 2 1
3 3 1
3 2 2
Output
5
Input
5
6 1 3
3 1 3
12 1 6
5 1 2
17 1 8
Output
3
Input
6
1 1 1
2 1 1
3 2 1
1 2 1
2 2 1
3 2 1
Output
7