题目描述

飞船最多可以携带 $M$ 份食品。现有 $N$ 份食品可供选择，共分为 $K$ 类。第 $i$ 类食品最多选择 $A_i$ 份。

第 $j$ 份食品的热量为 $E_j$，属于第 $T_j$ 类。每份食品最多选择一次。

请计算在不超过飞船容量和各类别数量限制的条件下，能够携带的最大总热量。

输入格式

第一行包含三个整数 $N,M,K$。

第二行包含 $K$ 个正整数 $A_1,A_2,\ldots,A_K$。

接下来 $N$ 行，每行包含两个整数 $E_j,T_j$，分别表示一份食品的热量和类别。

输出格式

输出一个整数，表示最大总热量。

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

35

数据范围与提示

• $1 \le N \le 100000$
• $1 \le M \le 50000$
• $1 \le K \le 50000$
• $1 \le A_i \le 100$
• $1 \le E_j \le 10000$
• $1 \le T_j \le K$