Bank Robbery 1

Interview

Time limit1sMemory limit256 MB

Summary

Given banks at positions X_i with open times T_i and rewards C_i, find the maximum total reward Siwoo can collect on one rightward path.

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

Problem

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

Siwoo starts at any integer coordinate on the line and moves. While he moves, the coordinate must increase. He cannot stop. Time starts at 0, and each time the coordinate increases by 1, the time increases by 1. When Siwoo reaches a bank whose door is open, he must rob it. He is so skilled that robbing a bank takes no time at all. Find the maximum amount of money Siwoo can get when he starts from a suitable position.

Input

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

From the second line on, the next $N$ lines each contain the integers $X_i, T_i, C_i$ , in increasing order of $i$ . Here $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 get.

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
```
11
```