小Q最近沉迷于《跳伞求生》游戏。

他组建了一支由 $n$ 名玩家（包括他自己）组成的战队，编号依次为 $1$ 到 $n$。这个游戏中，每局游戏开始时，所有玩家都会从飞机上跳伞，选择一个目的地降落，跳伞和降落的时间有早有晚。在某局游戏降落前，他们在空中观察发现地面上一共有 $m$ 间房子，编号依次为 $1$ 到 $m$。其中每间房子恰好有一名敌人早于他们到达。

小Q战队的第 $i$ 名玩家拥有 $a_i$ 发子弹，地面上第 $i$ 间房子里的敌人拥有 $b_i$ 发子弹，消灭他可以获得 $c_i$ 点积分。每名玩家必须且只能选择一间房子降落，然后去消灭里面的敌人。若第 $i$ 名玩家选择了第 $j$ 间房子，如果 $a_i>b_j$，那么他就可以消灭该敌人，获得 $a_i-b_j+c_j$ 的团队奖励积分，否则他会被敌人消灭。为了防止团灭，小Q不允许多名玩家选择同一间房子，因此如果某位玩家毫无利用价值，你可以选择让他退出游戏。因为房子之间的距离过长，你可以认为每名玩家在降落之后不能再去消灭其它房间里的敌人。

作为小Q战队的指挥，请制定一套最优的降落方案，使得最后获得的团队奖励总积分最大

输入格式

第一行包含两个正整数$n,m(1\le n,m\le 100000)$，分别表示战队的玩家数和地面上的房间数。

第二行包含n个正整数$a_1,a_2,\dots,a_n(1\le a_i\le 100000)$，分别表示每个玩家的子弹数。

接下来m行，每行两个正整数$b_i,c_i(1\le b_i,c_i\le 100000)$，分别表示每个敌人的子弹数和奖励积分。

输出格式

输出一行一个整数，即最后获得的团队奖励总积分的最大值。

样例输入

3 3
4 4 4
2 3
1 3
5 3

样例输出

11

数据范围

$10\%$的数据, $n, m\leq 7$。

$30\%$的数据 , $n, m\leq 13$。

$60\%$的数据 , $n, m\leq 1000$。

$100\%$的数据 , $3\leq n, m\leq 2 \times 10^ 5$。

时间限制：2s

内存限制：1GB