该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

B. 飞船补给

题目描述

小 A 在航空中心工作，他专门从事载人航天项目中宇航员的食物补给研发。这是一个重要而艰巨的任务。任务的目标是选择最佳的食物补给组合，在保持宇航员营养均衡的前提下，尽可能让宇航员摄入更多的热量。

某次飞行任务中，由于飞船存储空间有限，本次任务最多只能携带不超过 $M$ 份食物补给。这些食物可以从 $N$ 份航天食品中选择出若干份，搭配后作为宇航员的补给。

为了防止宇航员营养失衡，同一类的补给都不能过量的摄入。小 A 细心的将这些食物分成了 $K$ 个类别，经过精密计算，第 $i$ 类食物最多只能携带 $A_i$ 份。

请你编程帮助小 A 计算出，根据本题给出的数据，飞船能携带食物的最多总热量是多少？

输入

第 1 行读入三个整数 \(N,M,K\)，分别代表，一共有 $N$ 份不同的航天食物供任务选择，最多只能选择其中 $M$ 份，所有的食物一共分为 $K$ 类。 第 2 行读入 $K$ 个整数，第 $i$ 个整数 $A_i$ 代表第 $i$ 类食物最多可以携带 $A_i$ 份。 接下来 $N$ 行，每行有 2 个整数 $E_i,T_i$，代表了某食物可以提供的热量值为 $E_i$，该食物是第 $T_i$ 类食物。

输出

输出在飞船能携带食物的最多总热量的值。

样例

输入

5 4 1
3
10 1
12 1
8 1
6 1
20 1

输出

42

输入

8 2 3
1 2 3
15 3
16 1
17 2
18 3
10 1
12 3
13 1
14 2

输出

35

输入

12 5 4
1 2 3 4
2 3
3 3
5 3
6 3
6 2
3 2
12 4
18 4
36 4
17 4
19 4
30 1

输出

120

说明

【样例1解释】 共有 5 份食物，飞船最多只能携带 4 份，所有的食物分为 1 类。 第 1 类食物，最多只能携带 3 份。 因此，选择第 1 份、第 2 份、第 5 份食物，可以得到最大的总热量，最大的总热量的值 $= 10 + 12 + 20 = 42$。

数据范围

• 对于 20% 的数据，满足 $K = 1$。
• 对于 70% 的数据，满足 $1 \le N \le 200,\ 1 \le M \le 100,\ 1 \le K \le 100,\ 1 \le A_i \le 10,\ 1 \le E_i \le 100,\ 1 \le T_i \le K$。
• 对于 100% 的数据，满足 $1 \le N \le 10^5,\ 1 \le M \le 5\times 10^4,\ 1 \le K \le 5\times 10^4,\ 1 \le A_i \le 100,\ 1 \le E_i \le 10^4,\ 1 \le T_i \le K$。