单点时限: 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$。
输出一行,即最多卖出多少价值的闪卡。
2 6 1 2 1 2 1 3 1 4 2 1 2 3 1 7
13