페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5684

가짜 뉴스 2000초 512MB

문제

KOI 2차가 얼마 남지 않아 기자 준혁이는 취재를 시작했다.

N명의 참가자가 대회에 출전한다는 사실을 알게 된 준혁이는 인터뷰를 통해 i번째 참가자의 실력이 A_i번째 참가자보다는 크거나 같다는 사실을 알아내었다.

이때 A_i = i일 수 있다. (자신감이 넘치는 참가자들은 그렇게 말했다.)

보도를 위해서 준혁이는 각 참가자의 실제 실력 점수 H_i를 조사했다.

그런데 아무리 봐도 이 실력 점수는 앞선 인터뷰 결과와 맞지가 않는 것이다!

그래서 준혁이는 H_i를 인터뷰 결과에 맞춰 조작하기로 했다.

H_i를 1에서 10^9사이의 원하는 아무 숫자로 바꾸는 데는 C_i의 시간이 들어간다.

준혁이는 시간이 많이 없어서 최대한 빨리 조작을 마치고 보도하려고 한다.


입력

다음의 형식으로 입력이 주어진다.

N

A_1 H_1 C_1

\cdots

A_N H_N C_N

<제한>

  • 2 \le N \le 200000

  • 1 \le A_i \le N

  • 1 \le H_i, C_i \le 10^9

<서브 태스크>

  • #1 (14점) : N \le 5000, A_1 = 1, A_i \le i-1 (i >= 2)

  • #2 (65점) : A_1 = 1, A_i \le i-1 (2 \le i)

  • #3 (21점) : 추가 제한조건 없음.


출력

조작을 마치는데 필요한 최소 시간을 출력하라.


예제1

입력
6
165
136
184
349
225
256
출력
14

예제2

입력
5
111
221
431
331
431
출력
0

예제3

입력
20
17381792936
189964898447
127797240712
34299745243
218113181438
220952129455
434124298446
48933466733
740109601410
581902931267
24669879699
823785166502
81601717183
826747624379
117504589209
924909134233
1656236448090
894605526613
590481898834
934183442771
출력
2711043927

예제4

입력
20
1562418848971
135277275513
146080376452
1214256845164
1242481331310
686290168639
398947342135
319896070909
163948034188
829925729089
1897420006994
1351454182928
1961822405612
1337148425187
1577474094143
1427272926693
1843566552069
993790433300
107361654171
1428334498030
출력
4012295156

출처

JOI 2020/2021 Spring Training Camp 4-3번

역링크 공식 문제집만