밭에서 풀 키우기 2

프로 가드너가 된 JOI 군은 매년 자기 밭에서 IOI 풀을 기른다. 겨울에 IOI 풀의 씨를 뿌리면 봄에 싹이 나고 정해진 키까지 자란다. 일부 IOI 풀은 가을에 아름다운 열매를 맺는다. 열매를 맺은 IOI 풀은 수확된다. 열매를 맺지 않은 IOI 풀은 겨울에 죽는다.

JOI 군의 밭은 동서 방향으로 늘어선 $N$개의 구획으로 나뉘어 있다. 서쪽에서 $i$번째 구획 $i$에는 IOI 풀 $i$가 심어져 있다. IOI 풀 $i$는 봄에 키 $H_i$까지 자라고 그 뒤로는 자라지 않는다. IOI 풀 $i$가 열매를 맺으면 $P_i$엔에 거래된다. 열매를 맺지 않은 IOI 풀에는 상업적 가치가 없다.

봄에 밭을 살핀 JOI 군은 심어진 IOI 풀 일부를 뽑아서 거래로 얻는 이익을 최대화하려고 한다. IOI 풀 $i$ ($1 \le i \le N$)를 뽑으려면 $C_i$엔이 든다. 뽑은 IOI 풀은 죽는다. IOI 풀은 봄에만 뽑을 수 있고, 여름이나 가을에는 뽑을 수 없다.

IOI 풀은 여름에 햇빛을 많이 필요로 하는 식물이다. 어떤 구획의 IOI 풀에 대해, 번호가 더 작은 구획과 더 큰 구획 양쪽에 그 풀보다 키가 큰 IOI 풀이 여름에 심어져 있으면, 그 풀은 가을에 열매를 맺지 않는다. 즉, IOI 풀 $i$ ($1 \le i \le N$)가 뽑히지 않았을 때 가을에 열매를 맺는 경우는, 여름 단계에서 구획 $1, \ldots, i-1$에 IOI 풀 $i$보다 키가 큰 풀이 없거나, 구획 $i+1, \ldots, N$에 IOI 풀 $i$보다 키가 큰 풀이 없는 경우뿐이다.

열매를 맺은 IOI 풀의 거래 가격 합에서 IOI 풀을 뽑는 데 든 비용의 합을 뺀 값이 JOI 군의 이익이다. JOI 군이 IOI 풀로 얻을 수 있는 이익의 최댓값은 얼마인가?

밭과 그곳에 심어진 IOI 풀의 정보가 주어질 때, JOI 군이 얻을 수 있는 이익의 최댓값을 구하는 프로그램을 작성하라.

첫 줄에 JOI 군 밭의 구획 수를 나타내는 정수 $N$이 주어진다.

이어지는 $N$개의 줄 중 $i$번째 줄 ($1 \le i \le N$)에는 공백으로 구분된 정수 $H_i$, $P_i$, $C_i$가 주어진다. 이는 IOI 풀 $i$가 봄에 키 $H_i$까지 자라고, 가을에 열매를 맺었을 때 거래 가격이 $P_i$엔이며, 뽑는 데 $C_i$엔이 든다는 뜻이다.

JOI 군이 얻을 수 있는 이익의 최댓값을 정수 하나로 한 줄에 출력하라.

• $3 \le N \le 100000$
• $1 \le H_i \le 1000000000$ ($1 \le i \le N$)
• $1 \le P_i \le 1000000000$ ($1 \le i \le N$)
• $1 \le C_i \le 1000000000$ ($1 \le i \le N$)