题目描述

商店里有 $n$ 件商品，第 $i$ 件商品的价格为 $a_i$。店主希望将所有商品的价格统一，但又希望价格变动平稳。

具体来说，店主可以将某件商品 $i$ 的价格从 $a_i$ 调整为 $b_i$，要求新旧价格之差不超过 $k$，即满足 $|a_i - b_i| \le k$（其中 $|x|$ 表示 $x$ 的绝对值）。

每件商品的价格最多只能调整一次。注意，店主可以选择不调整某些商品的价格。每件商品的新价格 $b_i$ 必须为正整数（即对所有 $i$，都有 $b_i > 0$）。

你的任务是找出所有商品可以统一成的最大可能价格 $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$），表示每件商品的原价。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 个询问的答案 $B$。

如果无法将所有商品的价格统一为某个整数 $B$，使得对所有商品都满足 $|a_i - B| \le k$，则输出 $-1$。否则输出所有商品可能统一的最大价格 $B$。

说明/提示

在第一个样例询问中，可以选择价格 $B=2$。可以发现每个商品的原价与新价 $B=2$ 的差值都不超过 $1$。

在第二个样例询问中，可以选择价格 $B=6$，此时所有商品的原价与新价 $B=6$ 的差值都不超过 $2$。

在第三个样例询问中，无法选择任何合适的价格 $B$。对于任意 $B$，至少有一个条件不满足：$|1-B| \le 2$，$|6-B| \le 2$。

在第四个样例询问中，所有 $B$ 取值在 $1$ 到 $7$ 之间都合法，但最大值为 $7$，所以答案是 $7$。

由 ChatGPT 4.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