题目描述

星港外有一条只能向前行驶的巡航航道，一辆新能源巡检车要沿着航道尽可能远地前进。

这辆车装有 $n$ 个电瓶，第 $i$ 个电瓶充满时有 $a_i$ 单位电量。车辆每前进 $1$ 公里恰好消耗 $1$ 单位电量，你可以在行驶的每一公里自由选择由哪个还有电的电瓶供电。车辆不能后退。

出发前所有电瓶都是满电。沿途有 $m$ 个充电站，第 $j$ 个充电站距离起点 $x_j$ 公里，并且只能给第 $t_j$ 个电瓶充电。每个充电站提供的电量无限，但电瓶最多只能被充到满电。

请计算这辆车最远可以行驶多少公里。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含两个整数 $n,m$，表示电瓶个数和充电站个数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个电瓶的容量。

接下来 $m$ 行，每行包含两个整数 $x_j,t_j$，表示第 $j$ 个充电站的位置，以及它能给哪一个电瓶充电。

输出格式

对于每组测试数据，输出一行一个整数，表示车辆最远可以行驶多少公里。

样例

输入

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

输出

12
9

样例解释

对于第一组数据，车辆初始共有 $9$ 单位电量，可以到达 $8$ 公里处的充电站。到达前尽量消耗第 $1$ 个电瓶的电量，到达后再将第 $1$ 个电瓶充满，之后还能继续行驶 $4$ 公里，因此答案为 $12$。

对于第二组数据，车辆先在 $1$ 公里处给第 $2$ 个电瓶充电，再在 $2$ 公里处给第 $1$ 个电瓶充电，最终最远可以到达 $9$ 公里处。

数据范围

对于所有测试数据，满足：

• $1\le T\le 10^4$；
• $1\le n,m\le 10^5$；
• $1\le a_i\le 10^9$；
• $1\le x_1<x_2<\cdots<x_m\le 10^9$；
• $1\le t_j\le n$；
• 所有测试数据中，$n$ 之和与 $m$ 之和均不超过 $2\times 10^5$。

子任务

限制

时间限制：$1\text{s}$。

空间限制：$512\text{MB}$。