大雪球

今天是冬至，L 一边听着《葡萄成熟时》，一边在打雪仗。他发现他和对手实力悬殊，于是想到了一个方法：把两个不同的小雪球合成一个大雪球扔出去，这样雪球就具有更高的威力。

此时，L 手中还剩下 $n$ 个小雪球，其体积分别为 $v_1,v_2,\dots,v_n$。两个体积分别为 $x$ 和 $y$ 的小雪球可以合成一个体积为 $x+y$ 的大雪球。他想知道所有的合成方案中，体积第 $k$ 小的大雪球的体积是多少。两个合成方案不同当且仅当至少一个小雪球的序号不同。

测试点包含多组数据。第一行包含一个整数 $T$（$1\leq T\leq 10$），表示数据组数。每组数据的输入格式如下：

第一行包含一个整数 $n$（$2 \leq n\leq10^5$），表示小雪球的个数。

第二行包含 $n$ 个整数 $v_1,v_2,\dots,v_n$（$1\leq v_i\leq 10^9$），分别表示每个小雪球的体积。

第三行包含一个整数 $k$（$1\leq k\leq \frac{n(n-1)}2$），表示询问，其含义已在上文给出。

每组数据包含一个整数，表示体积第 $k$ 小的大雪球的体积。

1
4
2 3 4 5
3

7

样例中，可以合成 $6$ 种不同的大雪球，按体积排序后为 $[5,6,7,7,8,9]$，因此体积第 $3$ 小的大雪球的体积为 $7$。

“华为杯”杭州电子科技大学2023新生编程大赛