程序设计能力实训

1041. 闪卡销售

单点时限: 1.0 sec

内存限制: 256 MB

公司有 $n$ 种类型的闪卡要出售,闪卡类型编号为 $1,2,3,\ldots,n$,第 $i$ 种类型的闪卡数量为 $a_i$。

现有多个收购商给出的 $m$ 条关于闪卡的报价信息 $(p,q)$,表示收购第 $p$ 种类型的闪卡的单价为 $q$。

请计算公司如何销售,才能获得最多收益。

每个收购商可以收购无限量的闪卡。

输入格式

第一行输入两个整数 $n,m$ ($1 \le n,m \le 1000$),其中 $n$ 为闪卡类型数目,$m$ 为报价信息数目。

第二行输入 $n$ 个整数 $a_1, a_2, a_3, \ldots, a_n$,$a_i$ ($1 \le a_i \le 1000$) 表示第 $i$ 种类型闪卡数量。

接下来 $m$ 行,每行输入两个整数 $p,q$ ($1 \le p \le n, 1 \le q \le 1000$),表示第 $p$ 种类型的闪卡的报价 $q$。

输出格式

输出一行,即最多卖出多少价值的闪卡。

样例

Input
2 6
1 2
1 2
1 3
1 4
2 1
2 3
1 7
Output
13
不限期开放

题目列表