은행 털자 2

면접 대비

시간 제한1초메모리 제한256 MB

요약

각 은행의 X_i 위치와 문이 열리는 시각 T_i를 바탕으로, 오른쪽으로만 이동할 때 털 수 있는 최대 금액을 구합니다.

난이도: 쉬움10점 중 3점
유형: 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

프로 은행강도 시우가 은행을 털려고 한다. 시우가 달려가는 일직선 경로 위에 $N$ 개의 은행이 있다. $i$ 번째 은행은 직선상의 서로 다른 좌표 $X_i$ 에 있으며, 시간이 정확히 $T_i$ 일 때만 문이 열려 입장할 수 있다. 이 은행을 털면 $C_i$ 원을 얻을 수 있다.

시우는 직선상의 임의의 정수 좌표에서 시작해 움직인다. 움직이는 동안 좌표는 감소하지 않아야 한다 (원하는 만큼 멈춰 설 수 있다). 시간은 $0$ 에서 시작하며, 좌표가 $1$ 만큼 증가할 때 시간도 $1$ 만큼 증가한다.

시우는 문이 열린 은행을 마주치면 반드시 털고 지나간다. 매우 숙련되어 있어서 은행을 털어도 시간이 전혀 증가하지 않는다.

시우가 적절한 위치에서 출발했을 때 얻을 수 있는 최대 금액을 출력하라.

입력

첫 번째 줄에 $N$ 이 주어진다. ( $1 \le N \le 300\,000$ )

두 번째 줄부터 $N$ 개의 줄에 걸쳐 각 줄마다 $i$ 와 $X_i$ 가 증가하는 순서대로 정수 $X_i, T_i, C_i$ 가 주어진다. ( $0 \le X_i, T_i, C_i \le 10^9$ )

모든 $X_i$ 는 서로 다르다.

출력

시우가 얻을 수 있는 최대 금액을 출력한다.

예제3

예제 1
입력
```
1
0 3 4
```
예상 출력
```
4
```
예제 2
입력
```
2
0 0 10
1 0 3
```
예상 출력
```
10
```
예제 3
입력
```
5
0 2 4
1 6 1
2 4 4
3 8 10
4 5 2
```
예상 출력
```
18
```