Gold Camp Forcefield

Time limit1sMemory limit256 MB

Summary

Choose a contiguous group of camps whose total energy covers the distance between its ends to maximize total gold.

Level: Medium7 of 10
Topics: Segment tree, Prefix sum, Sorting
Solved: No attempts yet

Problem

Mansur plays a new computer strategy game. The main job in a game like this is mining resources. In this game only one resource matters for development, gold, and there is one supporting resource, energy.

The game has mining camps. Each camp supplies a fixed amount of gold and a fixed amount of energy, and all camps sit on one straight line. Camp $i$ is at coordinate $x_i$ and supplies $g_i$ gold and $d_i$ energy.

To protect camps, Mansur builds a forcefield. A forcefield is a closed segment on that line, and it needs an amount of energy equal to its length. A camp is protected when it lies inside the segment or on one of its endpoints, and only protected camps supply energy to the forcefield. The segment may have length $0$ .

Mansur builds one forcefield. The total energy of the protected camps must be at least the energy the forcefield needs, and the total gold of the protected camps must be as large as possible.

Write a program that finds the largest total gold Mansur can obtain from the protected camps.

Input

The first line contains one integer $N$ , the number of camps. Each of the next $N$ lines contains three space separated integers $x_i$ , $g_i$ , $d_i$ : the coordinate of the camp, the gold it supplies, and the energy it supplies.

$1 \le N \le 200\,000$
$0 \le x_i \le 10^9$
$1 \le g_i \le 10^9$
$1 \le d_i \le 10^9$

All $x_i$ are distinct and are given in increasing order.

Output

Print the largest total gold Mansur can obtain on one line.

Examples3

Example 1
Input
```
4
0 5 1
1 7 2
4 4 1
7 15 1
```
Expected output
```
16
```
Example 2
Input
```
2
0 4 1
3 5 1
```
Expected output
```
5
```
Example 3
Input
```
1
0 1 1
```
Expected output
```
1
```