No testdata at current.

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$ 个电池，每个电池能最多储存 $a_i$ 的单位电。每个电池的每一单位电能移动一单位距离，巡能指定每一个单位由哪个电池供应。

巡从原点出发，巡只能往前走。有 $m$ 个加油站，距离原点 $x_i$ 的地方有加油站，能把 $t_i$ 号电池的点充满。

当汽车所有电池都没电了，就不能动了。请告诉巡他最多能走多少单位的距离。

输入格式

第一行一个正整数 $T$ 表示测试数据数量。

每个测试点第一行两个正整数表示 $n,m$。

接下来一行 $n$ 个正整数表示 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行两个正整数表示 $x_i,y_i$。

输出格式

$T$ 行，每行一个正整数表示答案。

样例

【样例输入】

2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1

【样例输出】

12
9

数据范围

对所有数据 $1\leq T\leq 10$，$1\leq n,m\leq 2\times 10^5$。

特殊性质：$a_i=1$。