灰姑娘和她邪恶的继母正在玩一个游戏。灰姑娘最初有 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。这个游戏有两个参数 $A$ 和 $B$。

灰姑娘和继母轮流进行游戏，灰姑娘先手。每一轮，灰姑娘可以将序列 $a_1, a_2, \dots, a_n$ 替换为一个新的整数序列 $a'_1, a'_2, \dots, a'_n$，满足：

• $a'_1 \ge a_1, \dots, a'_n \ge a_n$
• $\sum_{i=1}^{n} a'_i \le \sum_{i=1}^{n} a_i + A$

然后继母可以选择 $B$ 个下标 $i_1, i_2, \dots, i_B$，并将 $a_{i_1}, a_{i_2}, \dots, a_{i_B}$ 设置为 $0$。

游戏无限进行下去。令 $M$ 为整个过程中 $a_1, a_2, \dots, a_n$ 的最大值。灰姑娘想要最大化 $M$，而继母想要最小化 $M$。

若双方都采取最优策略，确定 $M$ 的值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。对于每个测试用例： 第一行包含三个整数 $n, A, B$ ($1 \le B \le n \le 10^5, 0 \le A \le 10^{12}$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{12}$)。 保证 $\sum n \le 5 \times 10^5$。

输出格式

对于每个测试用例，输出一行包含一个整数：答案。

样例

样例输入

4
3 5 1
1 2 3
5 5 1
0 2 1 0 3
5 100 5
1 2 3 4 5
8 3 1
5 1 2 2 0 2 5 1

样例输出

11
14
105
9

说明

第一个测试用例的一种可能游戏过程： $\{1, 2, 3\} \to \{3, 4, 4\} \to \{3, 4, 0\} \to \{6, 6, 0\} \to \{6, 0, 0\} \to \{11, 0, 0\}$。