You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

小A购买了$n$件商品，每件商品的价格已知。商场发放了$m$张优惠券，每张优惠券的规则为"满$x$减$y$"，即当商品的原始总价（未使用任何优惠券时的总金额） 大于等于$x$时，该优惠券即可使用，减免$y$元。每张优惠券只能使用一次，且使用顺序不影响最终结果（所有满足原始总价条件的优惠券均可叠加使用）。

请计算小A最少需要支付的金额（结果保证非负）。

输入格式

第一行包含两个整数$n$和$m$，分别表示商品数量和优惠券数量。

第二行包含$n$个整数，依次表示每件商品的价格。

接下来$m$行，每行包含两个整数$x$和$y$，表示一张"满$x$减$y$"的优惠券。

输出格式

输出一个整数，表示小A最少需要支付的金额。

样例

样例输入

1 2  
100  
100 50  
80 30

样例输出

20

样例解释

商品原始总价为$100$元。 两张优惠券的满减条件$x$分别为$100$和$80$，均满足$100≥x$，因此可叠加使用。 总减免金额为$50+30=80$元，最终支付$100-80=20$元。

数据分布

设商品价格为 $a$

$40\%$的数据, $1 \le n,m \le 100$，$1 \le a \le 100$,$1 \le y \lt x \le 100$,

$100\%$的数据, $1 \le n,m \le 10^5$，$1 \le a \le 10^9$,$1 \le y \lt x \le 10^6$,

数据保证最终的答案非负。

时空限制

• 时间限制：$1s$
• 空间限制：$256M$