Menorca's ants
Description
Dani is one of the best competitive programmers in the world, boyfriend of the jambilla, best friend of Innokentiy and bodybuilder.
One day in Menorca, he left some cookies at his bed and a lot of ants spawned there.
Hugo and Luis said him to trow the bed through the window and Dani did it, but Ilya and the funator were be very angry with them.
Now Dani needs help with the following problem:
There are $n$ type of ants, and $a_{i}$ ants of the $i$-th type, you have to find the smallest number of moves to throw at least $p$ ants through the window.
Note that int each move Dani can throw at most $m$ ants and $k$ ants of the same type.
Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 10^{4})$. The description of the test cases follows.
The first line consists in three integers $n$, $m$, $k$ $(1 \leq n \leq 10^{6} ; 1 \leq m, k \leq 10^{18})$ — the number of types of ants, the maximum number of ants that can be thrown on a move and the maximum number of ants of the same type that can be thrown on a move, respectively.
Then follows $n$ integers $a_{1}, a_{2}, ..., a_{n}$ $(1 \leq a_{i} \leq 10^{12})$ — the number of ants of each type.
The last line consist in an integer $p$ $(1 \leq p \leq \sum_{i = 1}^{n} a_{i})$ — the minimum number of ants that have to be thrown.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{6}$.
For each testcase, output a single integer — the smallest number of moves.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 10^{4})$. The description of the test cases follows.
The first line consists in three integers $n$, $m$, $k$ $(1 \leq n \leq 10^{6} ; 1 \leq m, k \leq 10^{18})$ — the number of types of ants, the maximum number of ants that can be thrown on a move and the maximum number of ants of the same type that can be thrown on a move, respectively.
Then follows $n$ integers $a_{1}, a_{2}, ..., a_{n}$ $(1 \leq a_{i} \leq 10^{12})$ — the number of ants of each type.
The last line consist in an integer $p$ $(1 \leq p \leq \sum_{i = 1}^{n} a_{i})$ — the minimum number of ants that have to be thrown.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{6}$.
Output
For each testcase, output a single integer — the smallest number of moves.
4
4 3 2
3 7 2 1
13
3 2 2
2 2 3
6
2 3 2
10 1
10
1 1 1
1
1
5
3
5
1
Note
The answer for the first testcase could be $1$-st move: $(3, 2, 2)$, $2$-nd move: $(1, 2, 2)$, $3$-rd move: $(1, 2, 1)$, $4$-th move: $(2, 3, 4)$, $5$-th move: $(2)$.
It can be proven that at least $5$ moves are needed.
The answer for the second testcase could be $1$-st move: $(1, 1)$, $2$-nd move: $(2, 3)$, $3$-rd move: $(3, 3)$.
It can be proven that at least $3$ moves are needed.
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Novice 8, Advanced 4