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?
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$$$.
For each test case print a single line containing a single integer number. The minimum time Antwan needs to reach the enemy's camp
23 31 02 11 24 41 32 23 14 2
4 6