C. Отравленный кинжал
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в очередную компьютерную игру. В этой игре его персонаж должен убить дракона. Битва с драконом длится $$$100^{500}$$$ секунд, в течение которых Монокарп атакует дракона отравленным кинжалом. $$$i$$$-я атака происходит в начале $$$a_i$$$-й секунды от начала боя. Сам кинжал не наносит урона, но накладывает эффект яда на дракона, который наносит $$$1$$$ урона в течении следующих $$$k$$$ секунд (начиная с секунды, когда дракону был нанесен удар кинжалом). Однако, если дракон уже был отправлен ядом, то клинок обновляет эффект яда (т.е. отменяет действующий яд и накладывает новый).

Например, предположим, что $$$k = 4$$$, и Монокарп наносит удар дракону в секунды $$$2$$$, $$$4$$$ и $$$10$$$. Тогда эффект яда накладывается в начале $$$2$$$-й секунды и наносит $$$1$$$ урона в течение $$$2$$$-й и $$$3$$$-й секунд; затем, в начале $$$4$$$-й секунды, эффект яда накладывается повторно, поэтому он наносит $$$1$$$ урона в течение секунд $$$4$$$, $$$5$$$, $$$6$$$ и $$$7$$$; затем, на $$$10$$$-й секунде, снова накладывается эффект яда, и он наносит $$$1$$$ урона в течение секунд $$$10$$$, $$$11$$$, $$$12$$$ и $$$13$$$. В общей сложности дракон получает $$$10$$$ единиц урона.

Монокарп знает, что у дракона $$$h$$$ очков здоровья, и если он нанесет дракону хотя бы $$$h$$$ урона во время битвы — он убьет дракона. Монокарп еще не определился с силой яда, который он будет использовать во время боя, поэтому он хочет найти минимально возможное значение $$$k$$$ (количество секунд, в течение которых длится действие яда), которого достаточно, чтобы нанести дракону как минимум $$$h$$$ урона.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Первая строка набора содержит два целых числа $$$n$$$ и $$$h$$$ ($$$1 \le n \le 100; 1 \le h \le 10^{18}$$$) — количество атак Монокарпа и количество урона, которое необходимо нанести.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9; a_i < a_{i + 1}$$$), где $$$a_i$$$ — номер секунды $$$i$$$-й атаки.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное значение параметра $$$k$$$, при котором Монокарп нанесет дракону хотя бы $$$h$$$ урона.

Пример
Входные данные
4
2 5
1 5
3 10
2 4 10
5 3
1 2 4 5 7
4 1000
3 25 64 1337
Выходные данные
3
4
1
470
Примечание

В первом примере для $$$k=3$$$ урон наносится в секунды $$$[1, 2, 3, 5, 6, 7]$$$.

Во втором примере для $$$k=4$$$ урон наносится в секунды $$$[2, 3, 4, 5, 6, 7, 10, 11, 12, 13]$$$.

В третьем примере для $$$k=1$$$ урон наносится в секунды $$$[1, 2, 4, 5, 7]$$$.