Heroes of Might

최근 헬렌은 좋아하는 게임 "Heroes of Might"를 했다. 그녀는 Rust 드래곤 한 마리만 가진 영웅이었고, 농민을 많이 거느린 다른 영웅에게 공격을 받았다. 상대 영웅은 농민 그룹 $n$개를 가지고 있었고, $i$번째 그룹에는 $a_i$명의 농민이 있었다. 헬렌은 그 전투에서 졌다. 이제 그렇게 많은 농민 군대를 이기려면 Rust 드래곤의 체력이 얼마여야 하는지 알고 싶다.

전투는 다음과 같이 진행된다. 시작할 때 드래곤의 체력은 $h_d$이고, 농민 한 명의 체력은 $h_p$이다. 따라서 $i$번째 그룹의 전체 체력은 시작 시점에 $H = h_p \cdot a_i$이다. 전투는 여러 라운드로 이루어지며, 각 라운드에서 다음 두 가지가 일어난다.

• 먼저 드래곤이 농민 그룹 하나를 골라 공격한다. 그 그룹의 체력은 드래곤의 피해량 $d$만큼 줄어든다. 체력이 0 이하가 된 그룹은 파괴되어 게임에서 제외된다.
• 다음으로 남아 있는 농민 그룹들이 각각 드래곤을 공격한다. 현재 전체 체력이 $H$인 그룹에는 $\lceil\frac{H}{h_p}\rceil$명의 농민이 살아 있고, 각 농민이 드래곤의 체력을 1씩 줄인다.

드래곤의 체력이 어느 순간이든 0 이하가 되면 드래곤은 죽고 헬렌은 진다. 모든 농민 그룹이 파괴되면 헬렌이 이긴다.

헬렌이 매 턴 최적으로 공격 대상을 고를 때, 헬렌이 이길 수 있는 가장 작은 $h_d$를 구하라.

첫 줄에 테스트 케이스의 개수 $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$)가 주어진다. 둘째 줄에는 각 그룹의 농민 수 $a_i$ ($1 \le a_i \le 10^9$, $h_p \cdot \sum a_i \le 10^9$) $n$개가 주어진다.

모든 테스트 케이스에 걸친 $n$의 합은 1000을 넘지 않는다.

각 테스트 케이스마다 헬렌이 이기기 위해 드래곤이 가져야 하는 최소 체력 $h_d$를 한 줄에 출력한다. 농민이 드래곤에게 피해를 한 번도 주지 않는 경우에도 드래곤의 체력은 양수여야 하므로, 그때는 1을 출력한다.

세 번째 테스트 케이스에서 헬렌의 최적 전략은 다음과 같은 전투로 이어진다. 시작할 때 드래곤의 체력은 $h_d=26$이고, 농민 그룹 두 개의 체력은 $H_1=4\cdot10$, $H_2=5\cdot10$이다. 괄호 안에는 $\lceil\frac{H}{h_p}\rceil$의 값을 적어, $H_1=40(4)$, $H_2=50(5)$로 표기한다.