Description

最近，Hellen 玩了她最爱的游戏《英雄无敌》。她有一个只带了一条锈龙的英雄，结果被另一个带着大量农民的英雄攻击了。对方英雄有 $n$ 组农民，第 $i$ 组有 $a_i$ 个农民。不幸的是，Hellen 输掉了那场战斗，但现在她在思考：锈龙需要多少生命值才能击败这么庞大的农民军队？

让我们讨论战斗的流程。初始时，锈龙有 $h_d$ 点生命值，每个农民有 $h_p$ 点生命值。因此，第 $i$ 组农民在战斗开始时总共有 $H = h_p \cdot a_i$ 点生命值。战斗由若干回合组成，每回合发生以下两件事：

1. 锈龙选择一组农民并攻击它。该组的生命值减少 $d$ 点（$d$ 是锈龙的攻击力）。如果该组的生命值降至零或以下，它会被摧毁并从游戏中移除。
2. 每一组存活的农民都会攻击锈龙。当前总生命值为 $H$ 的组仍有 $\lceil\frac{H}{h_p}\rceil$ 个存活的农民，每个农民会减少锈龙 1 点生命值。

如果在任意时刻锈龙的生命值降至零或以下，它就会死亡，Hellen 输掉战斗。如果所有农民组都被摧毁，Hellen 获胜。

你需要求出最小的 $h_d$ 值，使得 Hellen 在每回合最优选择攻击目标的情况下能够获胜。

Input Format

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 需要解决的测试用例数量。

每个测试用例由两行描述。第一行包含三个数 $n$（$1 \le n \le 1000$）、$d$（$1 \le d \le 10^9$）和 $h_p$（$1 \le h_p \le 10^9$）—— 农民组的数量、锈龙的攻击力以及每个农民的生命值。第二行包含 $n$ 个数 $a_i$（$1 \le a_i \le 10^9$；$h_p \cdot \sum{a_i} \le 10^9$）—— 每组农民的数量。

所有测试用例的 $n$ 之和不超过 $1000$。

Output Format

对于每个测试用例，输出一个数 —— 锈龙需要的最小生命值 $h_d$，使得 Hellen 能获胜。如果农民从未攻击过锈龙，锈龙仍需保持正生命值，此时输出 $1$。

4
1 15 10
4
1 10 1
10
2 15 10
4 5
2 11 15
10 17

5
1
26
504

Hint

在第三个测试用例中，Hellen 的最优策略导致战斗流程如下：初始时，锈龙有 $h_d=26$ 点生命值，两组农民的生命值分别为 $H_1=4\cdot10$ 和 $H_2=5\cdot10$。我们用 $H_1=40(4)$ 和 $H_2=50(5)$ 表示，括号内是 $\lceil\frac{H}{h_p}\rceil$ 的值。

$$\begin{array}{c} h_d=26, H_1=40(4), H_2=50(5) & \text{第 1 回合} & \textbf{锈龙攻击第一组}，造成\ 15\ 点伤害，剩余\ H_1=25(3)。 \\ h_d=26, H_1=25(3), H_2=50(5) & & \text{农民攻击锈龙}，造成\ 3+5\ 点伤害，剩余\ h_d=18。 \\ h_d=18, H_1=25(3), H_2=50(5) & \text{第 2 回合} & \textbf{锈龙攻击第一组}，造成\ 15\ 点伤害，剩余\ H_1=10(1)。 \\ h_d=18, H_1=10(1), H_2=50(5) & & \text{农民攻击锈龙}，造成\ 1+5\ 点伤害，剩余\ h_d=12。 \\ h_d=12, H_1=10(1), H_2=50(5) & \text{第 3 回合} & \textbf{锈龙攻击第二组}，造成\ 15\ 点伤害，剩余\ H_2=35(4)。 \\ h_d=12, H_1=10(1), H_2=35(4) & & \text{农民攻击锈龙}，造成\ 1+4\ 点伤害，剩余\ h_d=7。 \\ h_d=7, H_1=10(1), H_2=35(4) & \text{第 4 回合} & \textbf{锈龙攻击第二组}，造成\ 15\ 点伤害，剩余\ H_2=20(2)。 \\ h_d=7, H_1=10(1), H_2=20(2) & & \text{农民攻击锈龙}，造成\ 1+2\ 点伤害，剩余\ h_d=4。 \\ h_d=4, H_1=10(1), H_2=20(2) & \text{第 5 回合} & \textbf{锈龙攻击第二组}，造成\ 15\ 点伤害，剩余\ H_2=5(1)。 \\ h_d=4, H_1=10(1), H_2=5(1) & & \text{农民攻击锈龙}，造成\ 1+1\ 点伤害，剩余\ h_d=2。 \\ h_d=2, H_1=10(1), H_2=5(1) & \text{第 6 回合} & \textbf{锈龙攻击第二组}，摧毁该组，将其从游戏中移除。 \\ h_d=2, H_1=10(1) & & \text{农民攻击锈龙}，造成 \ 1\ 点伤害，剩余\ h_d=1。 \\ h_d=1, H_1=10(1) & \text{第 7 回合} & \textbf{锈龙攻击第一组}，摧毁该组，将其从游戏中移除。 \\ h_d=1 & \text{战斗结束} & \text{锈龙存活，\ Hellen\ 获胜。} \end{array}$$

翻译由 DeepSeek V3 完成