B. The Amazing Adventures of Coffee Man!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

By day, Coffee Man is an ordinary office worker. But give him a cup of coffee and he becomes a superhero who can leap across the city in a single bound!

Coffee Man is standing at point $$$0$$$ of a number line, and he needs to get to point $$$n$$$ (reaching any point with coordinate at least $$$n$$$ is enough). He brought $$$m$$$ cups of coffee; the $$$i$$$-th cup initially has temperature $$$a_i$$$.

Every second, Coffee Man does exactly one of the following:

  • walk: his coordinate increases by $$$1$$$;
  • drink a cup he has not drunk yet: his coordinate increases by the current temperature of that cup.

Each cup can be drunk at most once. Unfortunately, coffee gets cold: after every second, the temperature of every cup decreases by $$$1$$$, but it never goes below $$$0$$$. In other words, if Coffee Man drinks the $$$i$$$-th cup when exactly $$$s$$$ seconds have passed, he moves forward by $$$\max(0, a_i - s)$$$.

What is the minimum number of seconds Coffee Man needs to reach a point with coordinate at least $$$n$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the coordinate Coffee Man needs to reach and the number of cups of coffee.

The second line of each test case contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_i \le 10^9$$$) — the initial temperatures of the cups.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum number of seconds Coffee Man needs to reach a point with coordinate at least $$$n$$$.

Example
Input
4
10 3
1 3 5
3 1
100
5 2
1 1
20 4
4 4 4 4
Output
5
1
5
14
Note

In the first test case, $$$n = 10$$$ and the temperatures are $$$[1, 3, 5]$$$. One optimal plan is:

  • second $$$1$$$: drink the cup with temperature $$$5$$$, moving to coordinate $$$5$$$;
  • second $$$2$$$: drink the cup that started at temperature $$$3$$$; it has cooled to $$$2$$$, so Coffee Man moves to coordinate $$$7$$$;
  • seconds $$$3$$$, $$$4$$$, $$$5$$$: walk, reaching coordinate $$$10$$$.

It is not possible to do better, so the answer is $$$5$$$. Note that drinking all three cups in the given order is worse: the cups give $$$1$$$, $$$2$$$ and $$$3$$$, so after $$$3$$$ seconds Coffee Man is at coordinate $$$6$$$ and needs $$$4$$$ more seconds of walking, $$$7$$$ seconds in total.

In the second test case, a single cup moves Coffee Man from $$$0$$$ to $$$100 \ge 3$$$.

In the third test case, the cups are useless: the first one moves him by $$$1$$$, which is no better than walking, and after that every cup has cooled down to $$$0$$$. The answer is $$$5$$$.

In the fourth test case, drinking all four cups gives $$$4+3+2+1=10$$$ units of movement in four seconds, after which walking takes ten more seconds. The total is $$$14$$$ seconds.