#216688. [MCO 2026] 知道得越少越好

龙 Evirir 写了关于信息学奥林匹克的 页内容。对于每个整数 ，恰好有一页的知识量为 。Evirir 将把这些页装订成一本书。形式化地，Evirir 会从 到 中选择一个长度为 的由互不相同整数组成的序列 。然后，它会制作一本书，使得第 页（）的知识量为 。

由于古老的龙族法律，某些页的知识量是固定的。法律规定了 个整数 。对于每个 ，如果 ，那么必须有 。满足 的 一共有 个。

Evirir 希望它的 个学生（编号为 ）阅读整本书。然而，由于注意力持续时间较短，每个学生 只会阅读第 页。一个学生的知识收益定义为该学生所阅读页面的知识量之和。

如果 Evirir 以最优方式装订这些页面，所有学生的总知识收益最大可以是多少？

第一行包含三个用空格分隔的整数 、 和 。

第二行包含 个用空格分隔的整数 。

接下来有 行，其中第 行包含两个用空格分隔的整数 和 。

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

样例输入 1

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

样例输出 1

15

样例输入 2

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

样例输出 2

10

样例输入 3

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

样例输出 3

20

提示

这个样例适用于子任务 1、4 和 6。

Evirir 写了 页，并且有 个学生。所有 页都是固定的。

• 学生 0 阅读第 0 到 2 页，获得的知识收益为 。
• 学生 1 阅读第 1 到 4 页，获得的知识收益为 。

因此，总知识收益为 。

这个样例适用于子任务 4 和 6。

有 页是固定的：0 和 3。一种最优的装订方式是 。

• 学生 0 阅读第 2 到 2 页，获得 的知识收益。
• 学生 1 阅读第 0 到 0 页，获得 的知识收益。
• 学生 2 阅读第 3 到 4 页，获得 的知识收益。

总知识收益为 。注意，可能还存在其他最优的装订方式。

一些 Evirir 不能选择的 的例子：

• ：第 0 页被固定为 ，但这里 。
• ：各页的知识量并非互不相同。
• ：各页的知识量必须在 到 之间。

这个样例适用于子任务 3、4 和 6。

由于 ，没有任何页的知识量是固定的。一种最优的装订方式是 。

• 学生 0 阅读第 1 到 3 页，获得的知识收益为 。
• 学生 1 阅读第 4 到 4 页，获得的知识收益为 。
• 学生 2 阅读第 0 到 4 页，获得的知识收益为 。

总知识收益为 。

评分

对于所有测试数据，输入满足以下限制：

• 对所有 ，有
• 恰好有 个 满足
• 所有固定值互不相同：如果 且 且 ，那么
• 对所有 ，有