Bank Robbery 2

Interview

Time limit1sMemory limit256 MB

Summary

Given banks at positions X_i that open at time T_i, find the maximum total money Siwoo can rob while moving only rightward from a chosen start.

Level: Easy3 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

Siwoo, a professional bank robber, wants to rob banks. Along the straight path he runs on, there are $N$ banks. The $i$ -th bank is at a distinct coordinate $X_i$ on the line, and its door opens only when the time is exactly $T_i$ , so he can enter only then. Robbing this bank yields $C_i$ won.

Siwoo starts at an arbitrary integer coordinate on the line and moves. While he moves, his coordinate must not decrease (he may stop as long as he wants). Time starts at $0$ , and whenever the coordinate increases by $1$ , the time increases by $1$ .

Whenever Siwoo meets a bank whose door is open, he must rob it and move on. He is very skilled, so robbing a bank never increases the time at all.

Print the maximum amount of money Siwoo can obtain when he starts at a suitable position.

Input

The first line contains $N$ . ( $1 \le N \le 300\,000$ )

From the second line onward, the next $N$ lines each contain integers $X_i, T_i, C_i$ in the order where $i$ and $X_i$ increase. ( $0 \le X_i, T_i, C_i \le 10^9$ )

All $X_i$ are distinct.

Output

Print the maximum amount of money Siwoo can obtain.

Examples3

Example 1
Input
```
1
0 3 4
```
Expected output
```
4
```
Example 2
Input
```
2
0 0 10
1 0 3
```
Expected output
```
10
```
Example 3
Input
```
5
0 2 4
1 6 1
2 4 4
3 8 10
4 5 2
```
Expected output
```
18
```