P7563 [JOISC 2021] 最悪の記者 4 (Worst Reporter 4) (Day4)

B 太郎不可爱。

B 太郎是一名主要写关于 OI 的报道的记者。再过几天，就要举行 IOI 了，B 太郎决定写一篇关于 IOI 的文章。 比赛将有 $n$ 名选手参加，每位选手的编号从 $1$ 到 $n$。每位选手都有一个 Rating，这是衡量其实力的标准。Rating 用 $1$ 至 $10^9$ 之间的整数表示。 B 太郎采访了每位选手，并获得了以下信息： - 选手 $i\ (1\le i\le N)$ 的 Rating 大于等于选手 $a_i\ (1\le a_i \le n)$ 的 Rating（$a_i$ 可以等于 $i$）。 在所有的采访结束后，B 太郎从管理 Rating 系统的公司收到了一张表格，上面有每个选手的 Rating。 表上写着以下信息： - 选手 $i\ (1 \le i \le n)$ 的 Rating 是 $h_i$。 当 B 太郎试图根据这些信息写一篇文章时，他发现每个选手的 Rating 表可能存在错误。 由于临近截止时间，没有时间去弄正确的 Rating 表。因此，B 太郎决定重写表中选手的 Rating，使其与采访中获得的信息不相矛盾。 B 太郎在表中改写选手 $i\ (1\le i \le n)$ 的 Rating 需要 $c_i$ 日元。 也就是说，B 太郎可以通过支付 $c_i$ 日元，将列表中选手 $i$ 的 Rating 更改为 $1$ 到 $10^9$ 之间的任意整数。为了在截止日期前完成任务，B 太郎想要最小化更改列表中 Rating 的总成本。 编写一个程序，给定选手的数量、采访获得的信息、Rating 列表、和更改每个选手 Rating 所用的花费。请你计算不与采访信息矛盾的情况下，最少需要花费多少日元。

无

无

#### 样例 #1 解释 如下表所示。 | 选手 | 原 Rating | 更改为 | 花费日元 | | :-: | :-: | :-: | :-: | | $1$ | $6$ | $1$ | $5$ | | $3$ | $8$ | $4$ | $4$ | | $5$ | $2$ | $10^9$ | $5$ | 花费了 $5+4+5=14$ 日元。 本样例满足 Subtask $1, 2, 3$。 #### 样例 #2 解释 信息一致，输出 $\tt 0$。 #### 样例 #3 解释 本样例满足 Subtask $1, 2, 3$。 #### 数据规模与约定 **本题采用 Subtask 计分法。** | Subtask | 分值占比百分率 | 特殊限制 | | :-: | :-: | :-: | | $1$ | $14\%$ | $n \le 5 \times 10^3$，$a_i = 1$，$a_i \le i - 1$，且 $2 \le i \le n$ | | $2$ | $65\%$ | $a_1 = 1$，$a_i \le i - 1$，且 $2 \le i \le n$ | | $3$ | $21\%$ | / | **注：斜线表示无特殊限制。** 对于 $100\%$ 的数据： - $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)$； #### 说明 本题译自 [第２０回日本情報オリンピック 2020/2021春季トレーニング合宿 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [競技 4 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/2021-sp-d4-notice.pdf) [T3 日文题面](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/worst_reporter4.pdf)。