题目描述

一辆新能源汽车配备了 $n$ 块电池，第 $i$ 块电池的容量为 $a_i$ 个单位。每一个电量单位可以让车辆行驶精确地 1 公里。车辆只能向前行驶，不能倒退。对于每公里行驶的选择，可以选择使用任意一块电池。

起初，所有电池都是满电状态。在行驶过程中，车辆将经过 $m$ 个充电站。第 $j$ 个充电站位于距离起点 $x_j$ 公里处，并且只能给第 $t_j$ 块电池充电。每个充电站提供无限量的电量。

你的任务是确定这辆新能源汽车最多可以行驶的距离。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量（$1 \leq T \leq 10^4$）。

对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$，分别表示电池的数量和充电站的数量（$1 \leq n, m \leq 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每块电池的容量（$1 \leq a_i \leq 10^9$）。

接下来的 $m$ 行中，每行包含两个整数 $x_j$ 和 $t_j$，表示每个充电站的位置以及它可以充电的电池编号（$1 \leq x_j \leq 10^9, 1 \leq t_j \leq n$）。

对于每个测试用例，保证 $1 \leq x_1 < x_2 < \dots < x_m \leq 10^9$。所有测试用例中 $n$ 或 $m$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示车辆最多可以行驶的距离。

样例

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

12
9