当前没有测试数据。

题目描述

小 $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
5 3
6 3
6 2
3 2
12 4
18 4
36 4
17 4
19 4
30 1

输出

120

数据范围

对于 $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$。