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.

题目内容

塔子哥最近在公司表现不错，老板奖励了他一堆优惠券。

正巧塔子哥需要购买一些生活用品，于是他来到了商场。

他购买了 $n$ 件商品，第 $i$ 件商品的价格为 $p_i$ 。

他有 $m$ 种优惠券，每种优惠券可以使用任意多次，但是每件商品只能使用一张优惠券

第 $i$ 种优惠券的使用条件为，当购买的一件商品的价格不低于 $a_i$ 时，可以减去 $b_i$ 的钱。

现在塔子哥问你，购买这 $n$ 种商品，他最少需要花多少钱。

输入描述

第一行，两个整数 $n,m(1\leq n,m\leq 2\times 10^5)$
第二行，$n$ 个整数 $p_i(1\leq p_i\leq 10^9)$ ，第 $i$ 个数为第 $i$ 件商品的价格。
接下来 $m$ 行，每行 $2$ 个整数，分别为 $a_i$ 和 $b_i(1\leq b_i<a_i\leq 10^9)$ ，含义见题面 。

输出描述

一个整数，表示塔子哥购买这 $n$ 种商品最少需要花的钱。

样例

输入

3 3
4 6 8
3 2
4 3
9 5

输出

9

说明

三件商品都使用第二种优惠券

总价格为 (4+6+8)-3-3-3=9