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

Вам дан массив целых чисел $$$a$$$ длины $$$n$$$.

Одна операция состоит из:

  • Выбора индекса $$$i$$$ такого, что $$$1 \le i \le n - 1$$$ и $$$a_i \le a_{i + 1}$$$.
  • Увеличения $$$a_i$$$ на $$$1$$$.

Найдите максимально возможное значение $$$\max(a_1, a_2, \ldots a_n)$$$, которое можно получить, выполнив эту операцию не более $$$k$$$ раз.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 1000$$$, $$$1 \le k \le 10^{8}$$$) — длина массива $$$a$$$ и максимальное количество операций, которых можно выполнить.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{8}$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$1000$$$.

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

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

Пример
Входные данные
6
3 4
1 3 3
5 6
1 3 4 5 1
4 13
1 1 3 179
5 3
4 3 2 2 2
5 6
6 5 4 1 5
2 17
3 5
Выходные данные
4
7
179
5
7
6
Примечание

В первом наборе входных данных одной возможной оптимальной последовательностью операций является: $$$[\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3]$$$.

Во втором наборе вдодных данных одной возможной оптимальной последовательностью операций является: $$$[1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$$$.