← 返回题目列表

Codeforces · 1183/B

B. 均衡价格

中文机器翻译题面 查看原题

商店里有 $$$n$$$ 产品。第 $$$i$$$ 个产品的价格为 $$$a_i$$$。店主希望所有产品的价格均等。不过,他希望能够顺利地改变价格。

事实上,店主可以更改某些产品 $$$i$$$ 的价格,使得该产品的旧价格 $$$a_i$$$ 与新价格 $$$b_i$$$ 之间的差异最多为 $$$k$$$。换句话说,条件 $$$|a_i - b_i| \le k$$$ 应该满足($$$|x|$$$ 是$$$x$$$ 的绝对值)。

他只能更改每种产品的价格一次。请注意,他可以保留某些产品的旧价格。每个产品 $$$i$$$ 的新价格 $$$b_i$$$ 应该为正(即 $$$b_i > 0$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 都应该满足)。

您的任务是找出所有产品的最大可能相等价格 $$$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$$$ 个整数是第 $$$i$$$ 个查询的答案 $$$B$$$。

如果不可能使所有给定产品的价格均等,但对于所有产品,条件 $$$|a_i - B| 的限制是不可能的。 \le k$$$ 应该满足(其中 $$$a_i$$$ 是产品的旧价格,$$$B$$$ 是所有产品的新同等价格),打印 -1。否则打印所有产品的最大可能同等价格。

示例

输入 #1

4
5 1
1 1 2 3 1
4 2
6 4 8 5
2 2
1 6
3 5
5 2 5

输出 #1

2
6
-1
7

注意

在第一个示例查询中,您可以选择价格 $$$B=2$$$。很容易看出,每个旧价格和每个新价格 $$$B=2$$$ 之间的差异不超过 $$$1$$$。

在第二个示例查询中,您可以选择价格 $$$B=6$$$,然后新旧价格 $$$B=6$$$ 之间的所有差异将不超过 $$$2$$$。

在第三个示例查询中,您无法选择任何合适的价格$$$B$$$。对于任何值$$$B$$$,至少会违反两个条件之一:$$$|1-B| \le 2$$$, $$$|6-B| \le 2$$$。

在第四个示例查询中,$$$1$$$ 和 $$$7$$$ 之间的所有值 $$$B$$$ 均有效。但最大值是$$$7$$$,所以这就是答案。