G1. Lakeside Trail (Easy Version)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The two versions differ only in the constraints on $$$n$$$, on the sum of $$$n$$$ over all test cases, and on the number of test cases.

A circular trail around a lake consists of $$$n$$$ sections numbered from $$$1$$$ to $$$n$$$ along the trail. The height of the $$$i$$$-th section is $$$h_i$$$. Sections $$$i$$$ and $$$i+1$$$ are adjacent for each $$$i$$$ from $$$1$$$ to $$$n-1$$$, and sections $$$n$$$ and $$$1$$$ are adjacent as well.

The steepness of the trail is the maximum absolute difference between the heights of two adjacent sections. In other words, the steepness is $$$\max_{1 \le i \le n} \left|h_i - h_{i+1}\right|$$$, where $$$h_{n+1}$$$ should be considered to exist and to be equal to $$$h_1$$$.

You have $$$k$$$ units of soil. One unit of soil increases the height of one section by $$$1$$$; several units may be used on the same section. Soil cannot be removed, so the heights can only increase.

Find the minimum possible steepness of the trail after using at most $$$k$$$ units of soil.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 2\cdot 10^3$$$, $$$0 \le k \le 10^{18}$$$) — the number of sections and the number of units of soil.

The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — the heights of the sections.

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

Output

For each test case, print a single integer — the minimum possible steepness of the trail after using at most $$$k$$$ units of soil.

Example
Input
6
4 3
1 5 2 8
5 5
2 9 4 1 6
3 0
1 4 7
3 100
1 10 1
5 5
4 1 1 1 1
6 14
3 6 2 4 1 5
Output
5
4
6
0
2
1
Note

In the first test case, you can use two units of soil on section $$$1$$$ and one unit on section $$$3$$$. The heights become $$$3, 5, 3, 8$$$, and the differences between adjacent sections are $$$2$$$, $$$2$$$, $$$5$$$, and $$$5$$$, the last one being between sections $$$4$$$ and $$$1$$$. So the steepness is $$$5$$$.

The ring is divided into four sections of the trail, with heights shown inside them. The $$$\Delta$$$ labels at the boundaries show the absolute differences between adjacent heights, and $$$+2$$$ and $$$+1$$$ show the added soil.

Steepness $$$4$$$ cannot be achieved: the height of section $$$4$$$ is at least $$$8$$$, and sections $$$3$$$ and $$$1$$$ are adjacent to it, so both of them would have to be raised to at least $$$4$$$, which needs $$$2 + 3 = 5$$$ units of soil.

In the second test case, the heights can become $$$5, 9, 5, 2, 6$$$ using $$$3 + 1 + 1 = 5$$$ units of soil, and the steepness becomes $$$4$$$. Steepness $$$3$$$ cannot be achieved: the height of section $$$2$$$ is at least $$$9$$$, so sections $$$1$$$ and $$$3$$$ would have to be raised to at least $$$6$$$, which needs $$$4 + 2 = 6$$$ units of soil.

In the third test case, no soil can be used. Sections $$$3$$$ and $$$1$$$ are adjacent, so the steepness is $$$7 - 1 = 6$$$.

In the fourth test case, all heights can be made equal to $$$10$$$ using $$$18$$$ units of soil.

In the fifth test case, the heights can become $$$4, 2, 1, 1, 2$$$ using $$$1 + 1 = 2$$$ units of soil, and the steepness becomes $$$2$$$. Steepness $$$1$$$ cannot be achieved: the height of section $$$1$$$ is at least $$$4$$$, and sections $$$2$$$ and $$$5$$$ are adjacent to it, so they would have to be raised to at least $$$3$$$, and then sections $$$3$$$ and $$$4$$$ to at least $$$2$$$, which needs $$$2 + 1 + 1 + 2 = 6$$$ units of soil.