题目描述

有一辆新能源汽车，这辆车有 $n$ 个电瓶，第 $i$ 个电瓶容量为 $a_i$ 单位，每消耗 $1$ 单位电力能恰好前进 $1$ 公里。车只能前进，不能反向行驶。你可以选择汽车行驶的每一公里所使用的电力来自哪个电瓶。

汽车在出发前每个电瓶都是充满电的。行驶中途会经过 $m$ 个充电站，第 $j$ 个充电站距离起点 $x_j$ 公里，并且只能给第 $t_j$ 个电瓶充电，每个充电站能提供的电力是无限的。

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

输入格式

第一行一个整数 $T$ ($1\le T\le 10^4$)，表示测试数据组数。

对于每组数据，第一行两个整数 $n, m$ ($1\le n,m\le 10^5$)，表示汽车电瓶个数和充电站的个数。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$)，分别表示每个电瓶的容量。

接下来 $m$ 行，每行两个整数 $x_j, t_j$ ($1\le x_j\le 10^9$, $1\le t_j\le n$)，分别表示每个充电站的位置和它能给哪个电瓶充电。

对于每组测试数据，保证 $1\le x_1<x_2<\ldots<x_m\le 10^9$。所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $2\cdot 10^5$。

输出格式

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

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

12
9