【JOISC2021】最差记者 4
Bitaro 是一位报道程序设计竞赛的专业记者。几天后会举办一次国际程序设计竞赛。Bitaro 准备写一篇文章报道此事。
这次竞赛会有 $N$ 名选手参加，他们从 $1$ 到 $N$ 编号。每名选手都有一个 rating 表明他们在程序设计竞赛中的能力。rating 是一个在 $1$ 和 $10^9$ 之间的整数（包括两端）。
Bitaro 已经采访了选手们。他获得了如下信息。
- 选手 $i\ (1\le i\le N)$ 的 rating 大于等于选手 $A_i$。这里可能会出现 $A_i=i$ 的情况。
在采访后。Bitaro 从管理 rating 系统的公司处获得了选手的 rating 列表。列表中写有如下信息。
- 选手 $i\ (1\le i\le N)$ 的 rating 等于 $H_i$。
Bitaro 试图基于以上信息写一篇报道。然而，rating 列表里选手的 rating 数据可能是有错误的。
因为截稿日马上就要到了，Bitaro 已经没有时间去获取正确的 rating 列表了。因此，Bitaro 决定更改列表中某些选手的 rating 数据，使得列表里的 rating 不会与采访中得到的信息矛盾。更改列表中选手 $i\ (1\le i\le N)$ 的 rating 的花费为 $C_i$。也就是说，Bitaro 可以在花费 $C_i$ 的代价下，将列表中选手 $i$ 的 rating 更改为 $1$ 到 $10^9$ 之间的任意整数（包括两端）。为了赶上截稿日，Bitaro 想要最小化更改 rating 的总花费。
给定选手数，采访中获得的信息，rating 列表和更改每个选手 rating 的花费。写一个程序计算使得 rating 列表不与采访获得信息矛盾的情况下，更改 rating 的最小总花费。
输入格式
第一行一个整数 $N$。
接下来 $N$ 行，每行三个整数 $A_i,H_i,C_i$。
输出格式
输出一行一个整数，表示最小总花费。
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
14
如果 Bitaro 按如下方法更改选手的 rating，那么得到的列表就不会与采访中得到的信息矛盾了。
- 将选手 $1$ 的 rating 由 $6$ 改为 $1$，花费为 $5$。
- 将选手 $3$ 的 rating 由 $8$ 改为 $4$，花费为 $4$。
- 将选手 $5$ 的 rating 由 $2$ 改为 $10^9$，花费为 $5$。
总花费为 $5+4+5=14$。因为这是最小的总花费，所以输出 $14$。
这组样例满足子任务 $1,2,3$ 的限制。
5
1 1 1
2 2 1
4 3 1
3 3 1
4 3 1
0
在这组样例中，列表中选手的 rating 与采访中获得的信息不矛盾，因此最小总花费为 $0$，输出 $0$。
样例三
这组样例满足子任务 $1,2,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
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
限制与约定
对于全部数据，满足：
- $2\le N\le 2\times 10^5$
- $1\le A_i\le N\ (1\le i\le N)$
- $1\le H_i,C_i\le 10^9\ (1\le i\le N)$
详细子任务附加限制及分值如下表所示：
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| $1$ | $N\le 5\ 000,\ A_1=1,\ A_i\le i-1\ (2\le i\le N)$ | $14$ |
| $2$ | $A_1=1,\ A_i\le i-1\ (2\le i\le N)$ | $65$ |
| $3$ | 无附加限制 | $21$ |
时间限制：$\texttt{2s}$
空间限制：$\texttt{512MB}$