说明

疯狂星期六指的是肯德基推出的新活动，意思就是说每周六肯德基会赠送一些优惠券，并且在星期六这一天，每张优惠券在满足某种菜品价格条件的情况下，那就可以使用在此菜品上，但是当天最多只能使用一张优惠券。

疯狂星期六活动：第 $i$ 个优惠券的使用条件是某种菜品满 $a_i$ 元钱，可以减 $b_i$ 元钱。

今天是星期六，小z 想把喜欢的 $n$ 种菜品各点一份，请问他这顿饭最少花费多少元钱？

输入格式

第一行包含两个整数 $n,m$ ，表示小z要点的 $n$ 种菜品以及当天赠送 $m$ 张优惠券。
第二行包含 $n$ 个整数 $ans_i$，表示第 $i$ 个菜品的价格为 $ans_i$ 元钱。

接下来 $m$ 行，每行包含两个整数 $a_i,b_i$ 代表第 $i$ 张优惠券的使用条件是：菜品满 $a_i$ 元钱，可以减 $b_i$ 元钱。

输出格式

输出一行一个整数 $sum$，表示小z这顿饭的最低花费。

样例

5 3
1 5 20 10 3
25 9
8 4
10 3

35

提示

第 $2$ 张优惠券使用在第 $3$个菜品上，所以最低花费为
$1+5+(20-4)+10+3=35$。

没有菜品的价格 $≥25$ 元，所以无法使用第一张优惠券。

【数据范围】
对于$100\%$的数据保证：$1 ≤ n,m ≤ 100，1 ≤ ans_i ≤  100，1 ≤ b_i ≤ a_i≤ 100$ 。
其中 $30\%$ 的数据存在无法使用优惠券的情况。