P14810 [CCPC 2024 Harbin Site] New Energy Vehicle

A new energy vehicle is equipped with $n$ batteries, where the $i$-th battery has a capacity of $a_i$ units. Each unit of electricity allows the vehicle to travel exactly $1$ kilometer. The vehicle can only go forward, not in reverse. You can choose which battery to use for each kilometer driven. Initially, all batteries are fully charged. During the journey, the vehicle will pass through $m$ charging stations. The $j$-th charging station is located at $x_j$ kilometers from the starting point and can only recharge the $t_j$-th battery. Each charging station provides an unlimited amount of electricity. Your task is to determine the maximum distance the new energy vehicle can travel.

The first line contains an integer $T$ ($1\le T\le 10^4$), representing the number of test cases. For each test case, the first line contains two integers $n, m$ ($1\le n,m\le 10^5$), representing the number of batteries and the number of charging stations, respectively. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$), representing the capacity of each battery. The next $m$ lines each contain two integers $x_j, t_j$ ($1\le x_j\le 10^9$, $1\le t_j\le n$), representing the position of each charging station and the battery it can recharge. For each test case, it is guaranteed that $1\le x_1

For each test case, output an integer in a single line, representing the maximum distance the vehicle can travel.