B. Приравнивание цен
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В магазине продается $$$n$$$ предметов. Цена $$$i$$$-го предмета равна $$$a_i$$$. Владелец магазина хочет приравнять цены всех предметов. Но он хочет изменить цены аккуратно.

Фактически, владелец магазина может изменять цену какого-то предмета $$$i$$$ таким образом, что разница между старой ценой этого предмета $$$a_i$$$ и новой ценой $$$b_i$$$ не превышает $$$k$$$. Другими словами, должно выполняться условие $$$|a_i - b_i| \le k$$$ ($$$|x|$$$ — это абсолютное значение $$$x$$$).

Он может изменять цену каждого предмета не более одного раза. Заметьте, что он может оставить старые цены некоторым предметам. Новая цена $$$b_i$$$ каждого предмета $$$i$$$ должна быть положительной (то есть должно выполняться условие $$$b_i > 0$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$).

Ваша задача — найти максимально возможную равную цену $$$B$$$ всех предметов с ограничением, что для всех предметов должно выполняться условие $$$|a_i - B| \le k$$$ (где $$$a_i$$$ равно старой цене предмета, а $$$B$$$ — это одинаковая новая цена всех предметов) или сказать, что невозможно найти такую цену $$$B$$$.

Заметьте, что выбранная цена $$$B$$$ должна быть целой.

Вам необходимо ответить на $$$q$$$ независимых запросов.

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

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

Первая строка запроса содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 100, 1 \le k \le 10^8$$$) — количество предметов и величину $$$k$$$. Вторая строка запроса содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$), где $$$a_i$$$ равно цене $$$i$$$-го предмета.

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

Выведите $$$q$$$ целых чисел, где $$$i$$$-е целое число является ответом $$$B$$$ на $$$i$$$-й запрос.

Если невозможно приравнять цены всех заданных предметов с ограничением, что для всех предметов должно выполняться условие $$$|a_i - B| \le k$$$ (где $$$a_i$$$ равно старой цене предмета, а $$$B$$$ равно новой равной цене всех предметов), выведите -1. Иначе выведите максимально возможную равную цену всех предметов.

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

В первом запросе тестового примера Вы можете выбрать цену $$$B=2$$$. Легко заметить, что разница между каждой старой ценой и новой ценой $$$B=2$$$ не превышает $$$1$$$.

В первом запросе тестового примера Вы можете выбрать цену $$$B=6$$$, тогда все разницы между старыми ценами и новыми ценами $$$B=6$$$ не превысит $$$2$$$.

В третьем запросе тестового примера Вы не можете выбрать никакую подходящую цену $$$B$$$. Для любого значения $$$B$$$ хотя бы одно условие из двух будет нарушено: $$$|1-B| \le 2$$$, $$$|6-B| \le 2$$$.

В четвертом запросе тестового примера все значения $$$B$$$ между $$$1$$$ и $$$7$$$ являются корректными. Но самое максимальное равно $$$7$$$, поэтому оно является ответом.