← 返回题目列表

Codeforces · 1904/C

C. 阵列游戏

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

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。在一次操作中,您必须选择一些 $$$(i, j)$$$ 使得 $$$1\leq i < j\leq |a|$$$ 并将 $$$|a_i - a_j|$$$ 附加到 $$$a$$$ 的末尾(即将 $$$n$$$ 增加 $$$1$$$ 并将 $$$a_n$$$ 设置为 $$$|a_i - a_j|$$$)。您的任务是在执行 $$$k$$$ 操作后最小化并打印 $$$a$$$ 的最小值。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2\le n\le 2\cdot 10^3$$$, $$$1\le k\le 10^9$$$) - 数组的长度和应执行的操作数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^{18}$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的$$$n^2$$$总和不超过$$$4\cdot 10^6$$$。

输出

对于每个测试用例,打印一个整数 - 执行 $$$k$$$ 操作后数组 $$$a$$$ 的最小值的最小可能值。

示例

输入 #1

4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000

输出 #1

1
0
3
500000000000000000

注意

在第一个测试用例中,在任何 $$$k=2$$$ 操作之后,$$$a$$$ 的最小值将为 $$$1$$$。

在第二个测试用例中,最佳策略是首先选择 $$$i=1, j=2$$$ 并附加 $$$|a_1 - a_2| = 3$$$ 到 $$$a$$$ 的末尾,创建 $$$a=[7, 4, 15, 12, 3]$$$。然后,选择 $$$i=3, j=4$$$ 并附加 $$$|a_3 - a_4| = 3$$$ 到 $$$a$$$ 的末尾,创建 $$$a=[7, 4, 15, 12, 3, 3]$$$。在最后的操作中,选择 $$$i=5, j=6$$$ 并附加 $$$|a_5 - a_6| = 0$$$ 到 $$$a$$$ 的末尾。那么 $$$a$$$ 的最小值将为 $$$0$$$。

在第三个测试用例中,最佳策略是首先选择 $$$i=2, j=3$$$ 附加 $$$|a_2 - a_3| = 3$$$ 到 $$$a$$$ 的末尾。任何第二次操作仍然不会使$$$a$$$的最小值小于$$$3$$$。