금 캐기 Batch Compilation commands

승현이는 새로 나온 컴퓨터 전략 게임을 즐겨 합니다. 이 게임에서 승현이는 자원을 캐는 일을 합니다. 운 좋게도 이 게임에서 캐야 할 자원은 금밖에 없고, 보충 자원으로 에너지가 있습니다.

이 게임에서는 채광 지역이 있어서, 어떤 양의 금과 에너지를 얻을 수 있습니다. 모든 지역은 일직선 상에 놓여 있습니다. 채광 지역을 보호하기 위해서 벽 (채광 지역들을 포함하는 선분) 을 세울 수 있고, 이를 세우는 데에는 벽의 길이만큼의 에너지가 필요합니다.

승현이는 단 하나의 벽을 지어서 이 벽에 의해 보호받는 지역들에서 나오는 에너지가 벽을 짓는 데에 충분하도록 할 때, 캘 수 있는 금의 양이 가능한 한 많았으면 합니다.

승현이가 얻을 수 있는 최대한의 금의 양이 얼마인지 구하는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에 채광 지역의 수 $N$이 주어집니다. 다음 $N$개 줄에 세 개의 정수 $x_{i}, g_{i}, d_{i}$가 주어집니다. ($0 \le x_{i} \le 10^{9}, 1 \le g_{i} \le 10^{9}, 1 \le d_{i} \le 10^9$) $x_{i}$는 채광 지역의 위치이고, $g_{i}$는 이 지역에서 나오는 금의 양, $d_{i}$는 이 지역에서 나오는 에너지의 양입니다. 모든 $x_{i}$는 서로 다르며 증가하는 순서대로 주어집니다.

출력 형식

승현이가 캘 수 있는 최대한의 금의 양을 구하세요.

서브태스크

서브태스크 1 (17점)

• $1 \le N \le 100.$

서브태스크 2 (31점)

• $1 \le N \le 5,000.$

서브태스크 3 (52점)

• $1 \le N \le 100,000.$

예제

예제 1

입력

4
0 5 1
1 7 2
4 4 1
7 15 1

출력

16

예제 2

입력

2
0 4 1
3 5 1

출력

5