题目描述

高桥非常喜欢胡椒。餐厅里有 $M$ 种胡椒，编号为 $1,2,\dots,M$，其中第 $j$（$1 \le j \le M$）种胡椒的存量为 $C_j$ 克。

高桥在这家餐厅点了 $N$ 道料理，出于口味搭配的要求，第 $i$（$1 \le i \le N$）道料理只能撒第 $A_i$ 种胡椒，且撒在这道料理上的胡椒量上限为 $B_i$ 克。

此外，高桥只能使用餐厅现有的胡椒，即第 $j$ 种胡椒的总使用量不能超过其存量 $C_j$ 克。

高桥希望合理分配每道料理的胡椒撒放量，使得所有料理的胡椒总使用量最大。请你求出这个最大的总使用量（单位：克）。

约束条件

所有输入均为整数

• $1 \le N,M \le 1000$
• $1 \le A_i \le M$
• $1 \le B_i,C_i \le 10^6$

输入格式

输入从标准输入给出，格式如下：

N M
C_1 C_2 … C_M
A_1 B_1
A_2 B_2
…
A_N B_N

输出格式

输出一个整数，表示胡椒的最大总使用量。

输入输出示例

示例 1

输入

7 5
4 4 8 3 7
1 2
2 3
5 2
4 10
2 3
5 4
2 3

输出

15

说明：该输入中有5种胡椒，存量依次为4、4、8、3、7克。按如下方式撒胡椒可得到最大总用量15克：

1. 第1道料理撒2克1号胡椒
2. 第2道料理不撒胡椒
3. 第3道料理撒2克5号胡椒
4. 第4道料理撒3克4号胡椒
5. 第5道料理撒1克2号胡椒
6. 第6道料理撒4克5号胡椒
7. 第7道料理撒3克2号胡椒

示例 2

输入

1 1
1
1 1

输出

1

示例 3

输入

15 10
7 94 100 82 63 81 75 2 76 73
10 44
5 77
10 47
7 32
2 82
5 90
3 37
6 70
6 28
3 25
2 26
10 56
1 69
5 46
7 26

输出

438