seuOJ513 - Nanami and the Boy

你和 Nanami 是通过一个游戏认识的。

桌子上一共有 $n$ 根绳子 $s$ ，每根绳子长度都为整数。每轮操作中，Nanami 和你都会做如下的操作：

Nanami 选择任意的两根绳子，把它们首尾拼接到一起。换句话来说，Nanami 选择任意的两根编号不同的绳子 $i,j$ ，创造出一根长度为 $s_k=s_i+s_j$ 的绳子 $k$ ，同时 $i,j$ 两根绳子会消失。

你需要选择任意一根长度大于 $1$ 的绳子，将这根绳子分成两根长度均为整数的绳子。换句话来说，你会选择一根长度大于 $1$ 的绳子 $k$ ，创造出两个长度分别为 $s_i,s_j$ 的绳子 $i,j$ ，且此时 $s_i+s_j=s_k$ ，同时绳子 $k$ 会消失。

已知你们两一共会进行 $x$ 轮操作，且每轮操作中由 Nanami 先手。Nanami 希望操作结束后所有绳子中最长的绳子的长度尽可能大，而你希望操作结束后所有绳子中最长的绳子的长度尽可能小。请问假如你们两每次都会做出最优决策，那么所有操作结束后，所有的 $n$ 根绳子中最长的绳子长度是多少。

第一行，一个整数 $t(1\le t\le 10^4)$ ，代表数据组数。

对于每组数据：

第一行，两个整数 $n,k(2\le n\le 5·10^5;1\le x\le 5·10^5)$ ，代表绳子的数量和操作的轮数。

第二行， $n$ 个整数 $s_1,\dots,s_n(1\le s_i\le 10^9)$ ，代表每根绳子的长度。

保证同一测试点内 $n$ 和 $x$ 的和均不会超过 $5·10^5$ 。

对于每组数据，输出一行整数，代表在 Nanami 和你两人每次都会做出最优决策的前提下，所有操作结束后，所有的绳子中最长的绳子长度是多少。

输入样例

5
3 1
1 2 3
5 100
5 5 5 5 5
8 2
1 3 2 5 6 10 3 6
6 3
1 1 1 1 1 4
2 2
1 1

输出样例