Description

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.

Input Format

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<x_2<\ldots<x_m\le 10^9$. Either the sum of $n$ or the sum of $m$ over all test cases does not exceed $2\cdot 10^5$.

Output Format

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

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

12
9