Bitaro 是一名专业记者，负责撰写关于程序设计竞赛的报道。几天后，一场国际程序设计竞赛即将举行，Bitaro 计划为该比赛撰写报道。
比赛共有 $N$ 名参赛选手，编号为 $1$ 到 $N$。每名选手都有一个称为“评分”（rating）的整数，用于衡量他们在程序设计竞赛中的实力。评分是 $1$ 到 $1\,000\,000\,000$ 之间的整数（包含边界）。
Bitaro 对选手们进行了采访，并获得了以下信息： 选手 $i$ ($1 \le i \le N$) 的评分大于或等于选手 $A_i$ ($1 \le A_i \le N$) 的评分。这里可能出现 $A_i = i$ 的情况。
采访结束后，Bitaro 从管理评分系统的公司收到了一份选手评分列表。列表中写着： 选手 $i$ ($1 \le i \le N$) 的评分为 $H_i$。
Bitaro 试图根据上述信息撰写报道。然而，他发现这份选手评分列表可能包含错误。
由于截止日期临近，Bitaro 没有时间获取正确的评分列表。因此，Bitaro 决定修改列表中某些选手的评分，使其不与采访中获得的信息相矛盾。在列表中修改选手 $i$ ($1 \le i \le N$) 评分的代价为 $C_i$。也就是说，Bitaro 可以支付 $C_i$ 的代价，将列表中选手 $i$ 的评分修改为 $1$ 到 $1\,000\,000\,000$ 之间的任意整数。为了赶上截止日期，Bitaro 希望最小化修改列表中评分的总代价。
请编写一个程序，在给定参赛选手人数、采访获得的信息、包含评分的列表以及修改每位选手评分的代价的情况下，计算出为了使评分不与采访信息相矛盾而修改列表中评分所需的最小总代价。
输入格式
从标准输入读取以下数据。所有给定的值均为整数。
$N$ $A_1$ $H_1$ $C_1$ $\vdots$ $A_N$ $H_N$ $C_N$
输出格式
向标准输出打印一行，输出最小总代价。
数据范围
- $2 \le N \le 200\,000$
- $1 \le A_i \le N$ ($1 \le i \le N$)
- $1 \le H_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
- $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
子任务
- (14 分) $N \le 5\,000$，$A_1 = 1$，$A_i \le i - 1$ ($2 \le i \le N$)。
- (65 分) $A_1 = 1$，$A_i \le i - 1$ ($2 \le i \le N$)。
- (21 分) 无附加限制。
样例
样例输入 1
6 1 6 5 1 3 6 1 8 4 3 4 9 2 2 5 2 5 6
样例输出 1
14
样例说明 1
如果 Bitaro 按以下方式修改列表中的选手评分，则不会与采访中获得的信息相矛盾： 将选手 1 的评分从 6 修改为 1。代价为 5。 将选手 3 的评分从 8 修改为 4。代价为 4。 * 将选手 5 的评分从 2 修改为 1 000 000 000。代价为 5。
总代价为 $5 + 4 + 5 = 14$。由于这是可能的最小值，输出 14。
样例输入 2
5 1 1 1 2 2 1 4 3 1 3 3 1 4 3 1
样例输出 2
0
样例说明 2
在此样例输入中，列表中的选手评分与采访中获得的信息并不矛盾。因此，最小总代价为 0。输出 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
样例输出 3
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
样例输出 4
4012295156