33OJ
登录 注册

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

[JAG 2026 Summer Camp #3] vs Hydra

题目描述

一只长有 NN 个头的九头蛇出现了。第 ii 个头最初有 HiH_i 点生命值。

你可以进行任意次攻击,包括零次。每次攻击时,从以下 N+1N+1 种类型中选择一种:

  • 攻击 ii(1≤i≤N1\le i\le N):使第 ii 个头的生命值减少 XX。
  • 攻击 N+1N+1:使每个头的生命值都减少 YY。

求使每个头的生命值都不大于 00 所需的最少攻击次数。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 TT(1≤T≤1001\le T\le100),表示测试数据的组数。接下来依次给出 TT 组测试数据,每组格式如下。

N X Y
H_1 H_2 ... H_N

每组测试数据的第一行包含三个整数 N,X,YN,X,Y(1≤N≤3×1051\le N\le3\times10^5,1≤X,Y≤10181\le X,Y\le10^{18}),分别表示头的数量、攻击 ii(1≤i≤N1\le i\le N)造成的伤害,以及攻击 N+1N+1 造成的伤害。

第二行包含 NN 个整数 H1,H2,…,HNH_1,H_2,\ldots,H_N(1≤Hi≤10181\le H_i\le10^{18}),其中 HiH_i 表示第 ii 个头的初始生命值。

所有测试数据的 NN 之和不超过 3×1053\times10^5。

输出格式

对于每组测试数据,输出一个整数,表示使每个头的生命值都不大于 00 所需的最少攻击次数。

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