은행 털자 1

면접 대비

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

요약

은행 N개의 위치 X_i, 문이 열리는 시각 T_i, 보상 C_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, 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
```
예상 출력
```
11
```