I. At War With The Army
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Antwan is a scout in the army at the frontline. He wants to get through the enemy's camp.

To reach the camp, Antwan needs to cross a cornfield of $$$n+2$$$ sectors numbered from $$$0$$$ to $$$n+1$$$. The enemy knew beforehand that some scouts might cross the field, so they planted $$$m$$$ self-detonating land mines, each land mine $$$i$$$ where $$$1 \le i \le m$$$ is placed at sector $$$a_i$$$ where $$$1 \le a_i \le n$$$ and will detonate after $$$b_i$$$ hours, killing every scout in sector $$$a_i$$$. Note that both sectors $$$0$$$ and $$$n+1$$$ does not have any land mines.

Antwan is currently at sector $$$0$$$ of the cornfield and the enemy's base is at sector $$$n+1$$$. He wants to cross the cornfield as fast as possible.

Antwan can go from sector $$$x$$$ to sector $$$x+1$$$ in one hour. Once he starts crossing the field, he can make $$$\textbf{at most one}$$$ stop at any sector he chooses (possibly at sector $$$0$$$) for as many hours as he wants, then he will continue crossing the cornfield. More formally, If Antwan wants to stop at sector $$$x$$$ for $$$y$$$ hours where $$$0 \le x \le n$$$ and $$$y \ge 0$$$, at hour $$$0$$$ he will be at sector $$$0$$$, at hour $$$1$$$ he will be at sector $$$1$$$ and so on, at hours $$$x, x+1 \dots x+y$$$ he will be at sector $$$x$$$, at hour $$$x+y+1$$$ he will be at sector $$$x+1$$$ and so on until he reaches sector $$$n+1$$$ where the enemy's camp lies.

Of course, Antwan does not want to be blown by a land mine. Nevertheless, he wants to reach the camp as soon as possible. What is the minimum time Antwan needs to reach the enemy's camp?

Input

The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 10^4)$$$. The number of test cases.

The first line of each test case contains two space-separated integer numbers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 10^6)$$$, where the cornfield has $$$n+2$$$ sectors and $$$m$$$ is the number of self-detonating land mines the cornfield has.

The next $$$m$$$ lines of each test case each contains two space-separated integer numbers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i \le n, 0 \le b_i \le 10^6)$$$. The sector where the $$$i$$$-th self-detonating land mine lies and the hour it will detonate at, respectively.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all of the test cases does not exceed $$$10^6$$$.

Output

For each test case print a single line containing a single integer number. The minimum time Antwan needs to reach the enemy's camp

Example
Input
2
3 3
1 0
2 1
1 2
4 4
1 3
2 2
3 1
4 2
Output
4
6