시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB62242444.444%

문제

Mansur plays the new computer strategic game. The main task in such games is mining resources. Fortunately in this game only one resource is necessary for development — the gold, and also there is one supplementary resource type — energy.

In this game there are mining camps, which provide certain amount of gold and energy. Аll camps are located along the straight line. To protect the mining camps one can build a forcefield (a closed line segment containing mining camps), which needs energy amount equal to it’s length.

Mansur wants to build one forcefield in such way, that energy of protected mining camps is enough for the forcefield, and amount of gold provided by these mining camps is maximal possible.

Write a program to help Mansur find the maximal amount of gold which he can obtain from protected mining camps.

입력

First line of the input file contains one integer N — number of mining camps. Following N lines contain three space separated integers xi, gi, di, 0 ≤ xi ≤ 109 , 1 ≤ gi ≤ 109 , 1 ≤ di ≤ 109: mine coordinates, amount of gold and energy provided by the mine. All xi are different and given in increasing order.

출력

Output only one number — maximal amount of gold which Mansur can mine.

서브태스크

번호배점제한
117

1 ≤ N ≤ 100

231

1 ≤ N ≤ 5000

352

1 ≤ N ≤ 100000

예제 입력 1

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

예제 출력 1

16

예제 입력 2

2
0 4 1
3 5 1

예제 출력 2

5

출처

Olympiad > International Zhautykov Olympiad > IZhO 2014 A번

  • 빠진 조건을 찾은 사람: yclock

채점 및 기타 정보

  • 예제는 채점하지 않는다.