你正在玩一款新的电子游戏，在游戏中你需要与 $n$ 个敌人战斗。第 $i$ 个敌人的攻击力为 $a_i$。你和敌人轮流行动。在每个回合中：

• 敌人先攻击。假设当前还剩 $x$ 个敌人，攻击力最低的 $k$ 个敌人会攻击你，并对你造成等同于它们攻击力之和的伤害。如果 $x < k$，则所有剩余的敌人都会攻击你。
• 然后轮到你行动。你有两个选择：要么消灭任意一个敌人，要么创建一个攻击力为 $m$ 的新敌人（$m$ 是一个固定常数）。

你的目标是消灭所有敌人，并使你受到的总伤害最小。注意，你也需要消灭你创建的那些敌人。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m, k$ ($1 \le k \le n \le 2 \times 10^5$, $0 \le m \le 10^6$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^6$)。

保证 $\sum n \le 2 \times 10^5$。

输出格式

对于每个测试用例，输出一个数字，表示你将受到的最小总伤害。

说明

在第一个样例中，你可以依次消灭第 4、3、2、1 个敌人，受到的伤害为 $(2 + 3 + 4) + (2 + 3 + 4) + (2 + 3) + (2) = 25$。

在第二个样例中，你可以创建一个攻击力为 1 的敌人，此时所有敌人的攻击力为 $\{1, 2, 3, 6, 7, 8\}$。然后你按顺序消灭它们，受到的伤害为 39。