33OJ
登录 注册

#P17577. [JAG 2026 Summer Camp #3] vs Hydra

[JAG 2026 Summer Camp #3] vs Hydra

Problem Description

A Hydra with NN heads has appeared. The ii-th head initially has HiH_i health points.

You may perform attacks any number of times, including zero. In each attack, choose one of the following N+1N+1 types:

  • Attack ii (1≤i≤N1\le i\le N): Decrease the health points of the ii-th head by XX.
  • Attack N+1N+1: Decrease the health points of every head by YY.

Find the minimum number of attacks required to make the health points of every head at most 00.

Input Format

The input contains one or more test cases. The first line of the input contains an integer TT (1≤T≤1001\le T\le100), which is the number of test cases. The descriptions of the TT test cases follow, each in the following format.

N X Y
H_1 H_2 ... H_N

For each test case, the first line contains three integers NN, XX, and YY (1≤N≤3×1051\le N\le3\times10^5, 1≤X,Y≤10181\le X,Y\le10^{18}), representing the number of heads, the damage dealt by Attack ii (1≤i≤N1\le i\le N), and the damage dealt by Attack N+1N+1, respectively.

The second line contains NN integers H1,H2,…,HNH_1,H_2,\ldots,H_N (1≤Hi≤10181\le H_i\le10^{18}), where HiH_i represents the initial health points of the ii-th head.

The sum of NN over all test cases does not exceed 3×1053\times10^5.

Output Format

For each test case, print a single integer representing the minimum number of attacks required to make the health points of every head at most 00.

2
3 5 2
12 6 17
1 998244353 1000000007
1000000007
7
1