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.

题目背景

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

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

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

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

题目描述

小 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$。