B. Equalizing
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We are given an array $$$a$$$ of $$$n$$$ integers and the integers $$$k$$$, $$$m$$$, $$$r$$$ (where $$$m \gt r \cdot (n-1)$$$). An operation consists of performing the following modifications for an index $$$1 \leq i \leq n$$$:

  • Add $$$m$$$ to $$$a_i$$$.
  • Subtract $$$r$$$ from all elements of $$$a$$$ except $$$a_i$$$, i.e., from $$$a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n$$$.

We can perform the above operation several times, for any index $$$1 \leq i \leq n$$$. It is not a problem if some elements become negative numbers after an operation.

Find the minimum number of operations needed to ensure that all elements of $$$a$$$ are greater than or equal to $$$k$$$.

Input

The first line contains $$$T$$$, the number of cases.

Each case begins with a line with four integers, $$$n$$$, $$$k$$$, $$$m$$$, and $$$r$$$.

The next line of each case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

Output

For each case, a line should be printed with the minimum number of operations needed to ensure that all elements of $$$a$$$ are greater than or equal to $$$k$$$.

Scoring
  1. (21 points) The sum over all cases of $$$k \cdot n^2$$$ is less than or equal to $$$10^5$$$.
  2. (23 points) $$$k \le 5 \cdot 10^3$$$.
  3. (56 points) No additional restrictions.
Example
Input
2
3 2 3 1
1 1 4
3 2 3 1
2 2 2
Output
2
0
Note

$$$1 \le T \le 10^3$$$.

$$$1 \le n \le 2 \cdot 10^3$$$.

$$$1 \le k, m, r, a_i \le 10^{6}$$$.

$$$m \gt r \cdot (n-1)$$$.

The sum of $$$n$$$ for all cases is at most $$$2 \cdot 10^3$$$.