P14810 [CCPC 2024 哈尔滨站] 新能源汽车

有一辆新能源汽车，这辆车有 $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

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