题目背景

冬雷震震起，惊梦两心连。

寒夜孤枕冷，思君倍觉暖。

天涯虽远隔，情意永不断。

风雪无尽时，相守到永远。

题目描述

小 T 喜欢玩三国杀，尤其是带小 Z 一起玩。

小 T 为自己设计了一个武将。

当小 T 使用这个武将时，若他的回合开始，$n$ 个敌方都会挂上『冬雷』标记。第 $i$ 个人有一个『冬雷』权值 $a_i$。

之后小 T 将会摸到 $m$ 张『铁索连环』，同时随机出 $m$ 个 $[1,n]$ 的数 $b_1,b_2,\dots,b_m$ 和 $m$ 个 $[1,10^9]$ 的数 $c_1,c_2,\dots,c_m$ 分配给这 $m$ 张『铁索连环』。

之后小 T 可依次使用这 $m$ 张铁索连环。第 $i$ 张『铁索连环』可以锁定至多 $b_i$ 名敌方，将被锁定的敌方的『冬雷』标记更新为 $c_i$。

回合结束时会引爆所有的『冬雷』标记，若敌方的冬雷标记为 $x$ 则小 T 将对其造成 $x$ 点伤害。

现在小 T 给了你这个回合的信息，请你帮小 T 算出这一回合他最多能造成多少伤害。

冬雷震震响，情意绵绵长。

输入格式

第一行，两个整数 $n,m$，表示本回合剩余敌方人数和小 T 获得的『铁索连环』个数。保证 $1\leq n,m\leq 10^5$

第二行，$n$ 个正整数 $a_i$ 表示回合开始时敌方获得的『冬雷』标记。保证 $1\leq a_i\leq 10^9$。

接下来 $m$ 行，每行两个整数 $b_i,c_i$ 表示第 $i$ 张『铁索连环』可以至多锁定 $b_i$ 名敌方，以及更新的『冬雷』标记值。

输出格式

一行，一个整数，表示小 T 这一回合最多能造成多少伤害。

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

338

11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

10000000001

提示

对于 $40\%$ 的数据，满足 $1\leq n,m\leq 100$；

对于 $60\%$ 的数据，满足 $1\leq n,m\leq 3000$；

对于 $100\%$ 的数据，满足 $1\leq n,m\leq 10^5$，$1\leq b_i\leq n$，$1\leq a_i,c_i\leq 10^9$。