C. Pizza Man
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a Pizza Man, who sells pizza, called Hosen.Hosen can store no more than $$$m$$$ pieces of pizza and initially he has $$$m$$$ pieces of pizza stored in his store.

There are $$$n$$$ customers; the $$$i_{th}$$$ of them will order $$$a_i$$$ pieces of pizza.

And Hosen has a positive integer $$$d$$$, that is when the number of pieces in the store is less than $$$d$$$, he refills it to $$$m$$$.

Here is a more detailed explanation.

When a customer orders $$$x$$$ pieces of pizza, the following happens:

  • If Hosen has at least $$$x$$$ pieces of pizza stored in the store, he sells $$$x$$$ pieces to the customer and now the pieces of pizza Hosen has will decrease by $$$x$$$. In this case, the customer will be happy.
  • If Hosen has less than $$$x$$$ pieces of pizza stored in the store, he sells all the remaining pieces of pizza to the customer and now he has zero pieces of pizza. In this case, the customer will be sad.
  • After serving each customer, if Hosen has less than $$$d$$$ pieces in the store, he will refill the store to have $$$m$$$ pieces of pizza.

You are given $$$m$$$,$$$n$$$ and the array of customers $$$a$$$; find the minimum value of $$$d$$$ for which all the customers will be happy.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n,m \le 2 \times 10^5)$$$.

The second line of each test case contains $$$n$$$ integers $$${a_1,a_2,\dots,a_n}$$$ $$$(1 \le a_i \le m)$$$, the elements of the array $$$a$$$.

Let $$$s$$$ be the sum of the array elements. It is guaranteed that the sum of $$$s$$$ overall test cases doesn't exceed $$$2 \times 10^5$$$.

Output

For each test case output a single positive integer $$$d$$$, the minimum value of $$$d$$$ for which all the customers will be happy.

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