题目背景

小维：“这么算是不是太贪心了？”

？？：“人不能没有钱嘛毕竟。”

题目描述

小维有编号 $1$ 到 $N$ 的共 $N$ 笔预算，第 $i$ 笔预算金额为 $A_i$ 。

现在小维合法获得了 $M$ 次修改金额的机会，对于所有机会，你都必须执行一次以下操作：

最多选择 $B_i$ 笔预算（可以选 $0$ 笔），用 $C_i$ 金额替换原来预算的金额。

小维比较笨，请问经过 $M$ 次操作后，$N$ 笔预算的最大可能总金额是多少？

输入描述

多测，第一行输入一个整数 $T (1 \leq T \leq 2 \cdot 10^5)$ ，代表测试组数。

对于每组测试数据：

第一行输入两个整数 $N,M(1 \leq N,M \leq 2 \cdot 10^5)$ ，表示共有 $N$ 笔预算，有 $M$ 次修改金额的机会。

第二行输入 $N$ 个整数 $A_1,A_2,...,A_N(1 \leq A_i \leq10^9,1\leq i \leq n)$ 。

接下来 $M$ 行，每行输入两个整数 $B_i,C_i(1 \leq B_i \leq N, 1 \leq C_i \leq 10^9, 1 \leq i \leq N)$ ，代表第 $i$ 次机会可以最多选择 $B_i$ 笔预算，用 $C_i$ 金额替换原来预算的金额。

保证所有测试数据的 $N$ 之和不超过 $2 \cdot 10^5$ 。

保证所有测试数据的 $M$ 之和不超过 $2 \cdot 10^5$ 。

输出描述

输出一个整数表示经过 $M$ 次操作后$N$笔预算的最大可能总金额。

样例

2
3 2
5 1 4
2 3
1 5
3 2
100 100 100
3 99
3 99

14
300