문제
KOI 2차가 얼마 남지 않아 기자 준혁이는 취재를 시작했다.
N명의 참가자가 대회에 출전한다는 사실을 알게 된 준혁이는 인터뷰를 통해 i번째 참가자의 실력이
이때
보도를 위해서 준혁이는 각 참가자의 실제 실력 점수
그런데 아무리 봐도 이 실력 점수는 앞선 인터뷰 결과와 맞지가 않는 것이다!
그래서 준혁이는
준혁이는 시간이 많이 없어서 최대한 빨리 조작을 마치고 보도하려고 한다.
입력
다음의 형식으로 입력이 주어진다.
<제한>
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
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
출력
14
예제2
입력
5
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1
출력
0
예제3
입력
20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
출력
2711043927
예제4
입력
20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030
출력
4012295156
출처
JOI 2020/2021 Spring Training Camp 4-3번