以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
ICPC 2021–2022, NERC – Northern Eurasia Finals
St. Petersburg, Almaty, Barnaul, Minsk, Yerevan, April 13th, 2022
Problem H. Heroes of Might
Time limit: 3 seconds
Memory limit: 512 megabytes
Recently, Hellen played her favorite game “Heroes of Might”. She had a hero with only one Rust dragon,
which was attacked by another hero with a lot of peasants. Another hero had n groups of peasants, i-th
of them had ai peasants in it. Unfortunately, Hellen lost that battle, but now she is wondering how big
the health of the Rust dragon should be to win against such a big army of peasants?
Let’s discuss how the battle goes. Initially, the Rust dragon has hd health points, and each peasant has
hp health points. So i-th group of peasants has a total of H = hp · ai health points at the start of the
battle. The battle consists of several rounds. In each round, two things happen:
• First, the dragon chooses one group of peasants and attacks it. The health of that group is
decreased by the dragon’s damage rating d. If the group has zero or less health points, it is destroyed
and is removed from the game.
• Second, each one of the peasant groups attacks the dragon. A group with the total current
health H has ⌈H ⌉peasants still alive and each of them decreases the dragon’s health by one. hp
If the dragon’s health becomes zero or less at any point, it dies and Hellen loses. If all peasant groups are
destroyed, Hellen wins the battle.
You need to determine the smallest possible hd, which could make Hellen win if she chooses targets on
each turn optimally.
Input
The first line of the input contains an integer t (1 ≤t ≤1000) — the number of test cases you need to
solve.
Each of the test cases is described by two lines. The first line contains three numbers n (1 ≤n ≤1000),
d (1 ≤d ≤109), and hp (1 ≤hp ≤109) — the number of peasant groups, the dragon’s damage rating, P
and the health of each peasant. The second line contains n numbers ai (1 ≤ai ≤109; hp · ai ≤109) —
the number of peasants in each group.
The sum of n over all test cases does not exceed 1000.
Output
For each test case, output one number — the smallest amount of health hd that the dragon should have
for Hellen to win the battle. If the dragon is never attacked by a peasant, it should still have positive
health, so output 1 in this case.
Example
standard input standard output
4 5
1 15 10 1
4 26
1 10 1 504
10
2 15 10
4 5
2 11 15
10 17
Note
In the third test case, the optimal Hellen’s strategy leads to the following battle. At the start, the dragon
Page 10 of 16
ICPC 2021–2022, NERC – Northern Eurasia Finals
St. Petersburg, Almaty, Barnaul, Minsk, Yerevan, April 13th, 2022
has hd = 26 health points, and two groups of peasants have H1 = 4 · 10 and H2 = 5 · 10 health points.
We’ll denote them as H1 = 40(4) and H2 = 50(5), placing the value of ⌈Hhp ⌉in the brackets.
hd = 26, H1 = 40(4), H2 = 50(5) Round 1 The dragon attacks the first group,
dealing 15 damage, leaving H1 = 25(3).
hd = 26, H1 = 25(3), H2 = 50(5) Peasants attack the dragon,
dealing 3 + 5 damage, leaving hd = 18.
hd = 18, H1 = 25(3), H2 = 50(5) Round 2 The dragon attacks the first group,
dealing 15 damage, leaving H1 = 10(1).
hd = 18, H1 = 10(1), H2 = 50(5) Peasants attack the dragon,
dealing 1 + 5 damage, leaving hd = 12.
hd = 12, H1 = 10(1), H2 = 50(5) Round 3 The dragon attacks the second group,
dealing 15 damage, leaving H2 = 35(4).
hd = 12, H1 = 10(1), H2 = 35(4) Peasants attack the dragon,
dealing 1 + 4 damage, leaving hd = 7.
hd = 7, H1 = 10(1), H2 = 35(4) Round 4 The dragon attacks the second group,
dealing 15 damage, leaving H2 = 20(2).
hd = 7, H1 = 10(1), H2 = 20(2) Peasants attack the dragon,
dealing 1 + 2 damage, leaving hd = 4.
hd = 4, H1 = 10(1), H2 = 20(2) Round 5 The dragon attacks the second group,
dealing 15 damage, leaving H2 = 5(1)
hd = 4, H1 = 10(1), H2 = 5(1) Peasants attack the dragon,
dealing 1 + 1 damage, leaving hd = 2.
hd = 2, H1 = 10(1), H2 = 5(1) Round 6 The dragon attacks the second group,
destroying it, so it is removed from the game.
hd = 2, H1 = 10(1) Peasants attack the dragon,
dealing 1 damage, leaving hd = 1.
hd = 1, H1 = 10(1) Round 7 The dragon attacks the first group,
destroying it, so it is removed from the game.
hd = 1 Game over The dragon is still alive, Hellen wins.
Page 11 of 16