P16699 [MCO 2026] 知道得越少越好

龙 Evirir 写了关于信息学奥林匹克的 $N$ 页内容。对于每个整数 $i = 0, 1, \ldots, N - 1$，恰好有一页的知识量为 $i$。Evirir 将把这些页装订成一本书。形式化地，Evirir 会从 $0$ 到 $N - 1$ 中选择一个长度为 $N$ 的由互不相同整数组成的序列 $A_0, A_1, \ldots, A_{N - 1}$。然后，它会制作一本书，使得第 $i$ 页（$0 \le i \le N - 1$）的知识量为 $A_i$。 由于古老的龙族法律，某些页的知识量是固定的。法律规定了 $N$ 个整数 $B_0, B_1, \ldots, B_{N - 1}$。对于每个 $0 \le i \le N - 1$，如果 $B_i \ne -1$，那么必须有 $A_i = B_i$。满足 $B_i \ne -1$ 的 $B_i$ 一共有 $K$ 个。 Evirir 希望它的 $M$ 个学生（编号为 $0, 1, \ldots, M - 1$）阅读整本书。然而，由于注意力持续时间较短，每个学生 $i$ 只会阅读第 $L_i, L_i + 1, \ldots, R_i$ 页。一个学生的知识收益定义为该学生所阅读页面的知识量之和。 如果 Evirir 以最优方式装订这些页面，所有学生的总知识收益最大可以是多少？

第一行包含三个用空格分隔的整数 $N$、$M$ 和 $K$。 第二行包含 $N$ 个用空格分隔的整数 $B_0, B_1, \ldots, B_{N - 1}$。 接下来有 $M$ 行，其中第 $i$ 行包含两个用空格分隔的整数 $L_i$ 和 $R_i$。

输出一个整数，表示所有学生可能获得的最大总知识收益。

### 提示 $\underline{样例\ 1}$ 这个样例适用于子任务 1、4 和 6。 Evirir 写了 $N = 5$ 页，并且有 $M = 2$ 个学生。所有 $K = N$ 页都是固定的。 - 学生 0 阅读第 0 到 2 页，获得的知识收益为 $3 + 4 + 1 = 8$。 - 学生 1 阅读第 1 到 4 页，获得的知识收益为 $4 + 1 + 0 + 2 = 7$。 因此，总知识收益为 $8 + 7 = 15$。 $\underline{样例\ 2}$ 这个样例适用于子任务 4 和 6。 有 $K = 2$ 页是固定的：0 和 3。一种最优的装订方式是 $A = [2, 0, 4, 1, 3]$。 - 学生 0 阅读第 2 到 2 页，获得 $4$ 的知识收益。 - 学生 1 阅读第 0 到 0 页，获得 $2$ 的知识收益。 - 学生 2 阅读第 3 到 4 页，获得 $1 + 3 = 4$ 的知识收益。 总知识收益为 $4 + 2 + 4 = 10$。注意，可能还存在其他最优的装订方式。 一些 Evirir 不能选择的 $A$ 的例子： - $A = [4, 0, 3, 1, 2]$：第 0 页被固定为 $B_0 = 2$，但这里 $A_0 = 4$。 - $A = [2, 4, 4, 1, 4]$：各页的知识量并非互不相同。 - $A = [2, 3, 5, 1, 4]$：各页的知识量必须在 $0$ 到 $N - 1$ 之间。 $\underline{样例\ 3}$ 这个样例适用于子任务 3、4 和 6。 由于 $K = 0$，没有任何页的知识量是固定的。一种最优的装订方式是 $A = [0, 4, 2, 1, 3]$。 - 学生 0 阅读第 1 到 3 页，获得的知识收益为 $4 + 2 + 1 = 7$。 - 学生 1 阅读第 4 到 4 页，获得的知识收益为 $3$。 - 学生 2 阅读第 0 到 4 页，获得的知识收益为 $0 + 4 + 2 + 1 + 3 = 10$。 总知识收益为 $7 + 3 + 10 = 20$。 ### 评分 对于所有测试数据，输入满足以下限制： - $1 \le N \le 5 \cdot 10^5$ - $1 \le M \le 10^5$ - $0 \le K \le N$ - 对所有 $0 \le i \le N - 1$，有 $-1 \le B_i \le N - 1$ - 恰好有 $K$ 个 $i$ 满足 $B_i \ne -1$ - 所有固定值互不相同：如果 $B_i \ne -1$ 且 $B_j \ne -1$ 且 $i \ne j$，那么 $B_i \ne B_j$ - 对所有 $0 \le i \le M - 1$，有 $0 \le L_i \le R_i \le N - 1$ | 子任务 | 分值 | 额外限制 | | :---: | :---: | :---: | | $1$ | $15$ | $N, M \le 5000$, $K = N$ | | $2$ | $10$ | $N, M \le 5000$, $K = 0$, 对所有 $0 \le i \le M - 1$，$(L_i, R_i) = (L_0, R_0)$ | | $3$ | $25$ | $N, M \le 5000$, $K = 0$ | | $4$ | $15$ | $N, M \le 5000$ | | $5$ | $10$ | 对所有 $0 \le i \le M - 1$，$L_i = 0$ | | $6$ | $25$ | -- |