题目描述

你转生到了异世界，成为了一名勇者。为了伸张正义，你将和一条巨龙结伴，一同打倒邪恶的农民。

异世界中共有 $n$ 组农民，第 $i$ 组有 $a_i$ 个小兵。巨龙与农民的战斗按照下述方式进行。

最初，巨龙有 $h_d$ 点血量，每个敌方小兵都有 $h_p$ 点血量。因此，第 $i$ 组小兵在战斗开始时的总血量为

战争由若干轮战斗组成。每一轮依次发生以下两件事：

1. **巨龙选择一组小兵并攻击它们。**该组的总血量减少 $d$，最低降至 $0$。如果该组的总血量变为 $0$，则该组农民覆灭。

2. **每组仍存活的小兵攻击巨龙。**一个总血量为 $H$ 的农民组中，仍有

   $$\left\lceil\frac{H}{h_p}\right\rceil$$

   个小兵存活，每个存活的小兵都会对巨龙造成 $1$ 点伤害。

如果巨龙的生命值在任何时刻变为 $0$ 或更低，它就会死亡，你也就输了。如果所有小兵都被消灭，则你获胜。

请确定尽可能小的 $h_d$，使得存在一种策略能够赢得战斗。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 $T$，表示测试数据组数。

接下来依次给出每组测试数据。每组测试数据包含两行：

• 第一行包含三个整数 $n,d,h_p$，分别表示小兵组数、巨龙的攻击力以及每个小兵的血量；
• 第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 组小兵的初始数量。

输出格式

对于每组测试数据，输出一行一个正整数，表示巨龙赢得战斗所需的最小初始血量 $h_d$。

注意，即使巨龙从未受到攻击，它的血量也必须始终为正整数，因此答案至少为 $1$。

样例 1

输入

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

输出

5
1
26
504

数据范围

对于全部测试数据，保证：

• 对于单组测试数据，

  $$1\le n\le 1000,\qquad 1\le d,h_p,a_i\le 10^9,$$ $$h_p\cdot\sum a_i\le 10^9;$$

• 所有测试数据中的 $n$ 之和满足

  $$\sum n\le 1000.$$