题目描述

龙 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$。

输出格式

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

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

15

5 3 2
2 -1 -1 1 -1
2 2
0 0
3 4

10

5 3 0
-1 -1 -1 -1 -1
1 3
4 4
0 4

20

提示

提示

$\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$