Bitaro là một phóng viên chuyên viết bài về các kỳ thi lập trình. Vài ngày nữa sẽ diễn ra một kỳ thi lập trình quốc tế, và Bitaro đang chuẩn bị viết bài về kỳ thi này.

Có \(N\) thí sinh, được đánh số từ \(1\) đến \(N\). Mỗi thí sinh có một điểm xếp hạng, là số nguyên từ \(1\) đến \(1\,000\,000\,000\), thể hiện năng lực lập trình thi đấu của người đó.

Qua phỏng vấn các thí sinh, Bitaro biết rằng với mỗi \(i\) (\(1\le i\le N\)), điểm xếp hạng của thí sinh \(i\) lớn hơn hoặc bằng điểm xếp hạng của thí sinh \(A_i\) (\(1\le A_i\le N\)). Có thể xảy ra \(A_i=i\).

Sau các cuộc phỏng vấn, một công ty quản lý hệ thống xếp hạng gửi cho Bitaro danh sách ghi rằng điểm xếp hạng của thí sinh \(i\) là \(H_i\). Tuy nhiên, khi định viết bài dựa trên các thông tin này, Bitaro nhận ra rằng danh sách có thể chứa lỗi.

Hạn nộp bài đã gần kề nên Bitaro không còn thời gian lấy danh sách chính xác. Cậu quyết định sửa điểm xếp hạng của một số thí sinh trong danh sách để danh sách không mâu thuẫn với bất kỳ thông tin nào thu được từ các cuộc phỏng vấn.

Với chi phí \(C_i\), Bitaro có thể đổi điểm xếp hạng của thí sinh \(i\) trong danh sách thành một số nguyên bất kỳ từ \(1\) đến \(1\,000\,000\,000\). Hãy tính tổng chi phí nhỏ nhất để sửa danh sách sao cho thỏa mãn tất cả các thông tin phỏng vấn.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng:

N
A_1 H_1 C_1
...
A_N H_N C_N

Mọi giá trị đầu vào đều là số nguyên.

Dữ liệu ra

Xuất một dòng chứa tổng chi phí nhỏ nhất.

Ràng buộc

• \(2\le N\le 200\,000\).
• \(1\le A_i\le N\) với mọi \(1\le i\le N\).
• \(1\le H_i\le 1\,000\,000\,000\) với mọi \(1\le i\le N\).
• \(1\le C_i\le 1\,000\,000\,000\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(14\) điểm: \(N\le 5000\), \(A_1=1\) và \(A_i\le i-1\) với mọi \(2\le i\le N\).
2. \(65\) điểm: \(A_1=1\) và \(A_i\le i-1\) với mọi \(2\le i\le N\).
3. \(21\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

14

5
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1

0

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

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

Nguồn

JOI 2020/2021, Spring Training Camp, Contest 4. Tác giả: 戸髙空. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.