最近，Hellen 玩了她最喜欢的游戏“Heroes of Might”。她拥有一条锈蚀龙（Rust dragon），而另一位英雄带着大量农民来攻击它。对方有 $n$ 组农民，第 $i$ 组有 $a_i$ 个农民。不幸的是，Hellen 在那场战斗中输了，但现在她想知道，锈蚀龙需要多少生命值才能在面对如此庞大的农民军队时获胜？

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

• 首先，龙选择一组农民并攻击它。该组农民的生命值减少龙的攻击力 $d$。如果该组农民的生命值降至零或以下，则该组被消灭并从游戏中移除。
• 其次，每一个农民组攻击龙。对于一个当前总生命值为 $H$ 的农民组，仍有 $\lceil \frac{H}{h_p} \rceil$ 个农民存活，且每个存活的农民会使龙的生命值减少 1 点。

如果龙的生命值在任何时刻降至零或以下，它就会死亡，Hellen 输掉比赛。如果所有农民组都被消灭，Hellen 赢得战斗。

你需要确定最小的 $h_d$，使得如果 Hellen 在每一轮都做出最优的攻击选择，她能够获胜。

输入格式

输入的第一行包含一个整数 $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 a_i \le 10^9$)，表示每组农民的数量。

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

输出格式

对于每个测试用例，输出一个数字，表示龙为了获胜所需的最小生命值 $h_d$。如果龙从未受到农民的攻击，它仍需拥有正数生命值，因此在这种情况下输出 1。

样例

输入 1

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

输出 1

5
1
26
504

说明

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

$h_d = 26, H_1 = 40(4), H_2 = 50(5)$ 第 1 轮：龙攻击第一组，造成 15 点伤害，剩余 $H_1 = 25(3)$。农民攻击龙，造成 $3 + 5$ 点伤害，剩余 $h_d = 18$。

$h_d = 18, H_1 = 25(3), H_2 = 50(5)$ 第 2 轮：龙攻击第一组，造成 15 点伤害，剩余 $H_1 = 10(1)$。农民攻击龙，造成 $1 + 5$ 点伤害，剩余 $h_d = 12$。

$h_d = 12, H_1 = 10(1), H_2 = 50(5)$ 第 3 轮：龙攻击第二组，造成 15 点伤害，剩余 $H_2 = 35(4)$。农民攻击龙，造成 $1 + 4$ 点伤害，剩余 $h_d = 7$。

$h_d = 7, H_1 = 10(1), H_2 = 35(4)$ 第 4 轮：龙攻击第二组，造成 15 点伤害，剩余 $H_2 = 20(2)$。农民攻击龙，造成 $1 + 2$ 点伤害，剩余 $h_d = 4$。

$h_d = 4, H_1 = 10(1), H_2 = 20(2)$ 第 5 轮：龙攻击第二组，造成 15 点伤害，剩余 $H_2 = 5(1)$。农民攻击龙，造成 $1 + 1$ 点伤害，剩余 $h_d = 2$。

$h_d = 2, H_1 = 10(1), H_2 = 5(1)$ 第 6 轮：龙攻击第二组，将其消灭并从游戏中移除。农民攻击龙，造成 1 点伤害，剩余 $h_d = 1$。

$h_d = 1, H_1 = 10(1)$ 第 7 轮：龙攻击第一组，将其消灭并从游戏中移除。

$h_d = 1$ 游戏结束：龙仍然存活，Hellen 获胜。