금광 캠프 방어막

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

요약

보호 구간의 양 끝 거리 이상의 에너지를 내는 연속된 캠프 구간 중 금 합이 최대가 되는 값을 구합니다.

문제

만수르는 새로 나온 컴퓨터 전략 게임을 한다. 이런 게임에서 가장 중요한 일은 자원 채굴이다. 다행히 이 게임에서 발전에 필요한 자원은 금 하나뿐이고, 보조 자원으로 에너지가 있다.

게임에는 채굴 캠프가 있다. 각 캠프는 정해진 양의 금과 에너지를 공급하고, 캠프는 모두 하나의 직선 위에 놓여 있다. $i$ 번 캠프는 좌표 $x_i$ 에 있고 금 $g_i$ 와 에너지 $d_i$ 를 공급한다.

캠프를 보호하려면 방어막을 세우면 된다. 방어막은 캠프를 포함하는 닫힌 선분이고, 길이와 같은 양의 에너지가 필요하다. 선분 안쪽이나 양 끝점에 놓인 캠프가 보호받는 캠프이며, 보호받는 캠프만 방어막에 에너지를 공급한다. 선분의 길이는 $0$ 일 수도 있다.

만수르는 방어막을 하나 세우려고 한다. 보호받는 캠프가 공급하는 에너지의 합이 방어막에 필요한 에너지 이상이어야 하고, 그러면서 보호받는 캠프가 공급하는 금의 합이 최대여야 한다.

보호받는 캠프에서 얻을 수 있는 금의 최대 합을 구하는 프로그램을 작성하라.

첫 줄에 캠프의 개수 $N$ 이 주어진다. 다음 $N$ 개의 줄에 세 정수 $x_i$ , $g_i$ , $d_i$ 가 공백으로 구분되어 주어진다. 차례대로 캠프의 좌표, 캠프가 공급하는 금, 캠프가 공급하는 에너지다.

$x_i$ 는 모두 다르고, 증가하는 순서로 주어진다.

만수르가 얻을 수 있는 금의 최대 합을 한 줄에 출력한다.