# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Harry and Hermione - 2

By Apurba.884537 · Limits 1s, 512 MB

[1 and 2 are completely different problems. Consider reading both.]

The monsters are back again. Harry and Hermione are fighting the monsters. There are $n$ monsters, and their health point is described by an array $h$ consisting of $n$ positive integers. A monster is dead when its health point becomes non-positive ($\le 0$).

To fight these monsters, Harry knows a spell which can be casted over a single monster and has power $x$. On the other hand, Hermione knows a spell which can be casted over multiple monsters and has power $y$.

Initially, $y = 1$ and $x$ is given in the input.

Starting from day $1$, the following happens in each day in the order mentioned:

1.     Harry selects a monster, and deals $x$ damage to that monster. [It is possible to select a monster which is already dead]

2.     Hermione casts her spell over all the other monsters (excluding the one Harry selected) and deals $y$ damage to each of these monsters.

3.     $x$ is increased by $1$.

4.     $y$ is increased by $1$.

If Harry and Hermione fight optimally, calculate the minimum number of days needed to kill all the monsters.

## Input

The first line of the input contains a single integer $t (1\le t \le 10000)$ — the number of test cases.

Each test case consists of two lines. The first line contains two integers $n$ and $x$ $(1 \le n \le 2 \times 10^5 ; 2 \le x \le 10^9)$ — the number of monsters and initial power of Harrys spell respectively.

The second line contains $n$ integers $h_1,h_2,\ldots,h_n$  $(1 \le h_i \le 10^9)$ — initial health point of each monster.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

## Output

For each test case, print a single integer — minimum number of days needed to kill all the monsters.

## Sample

InputOutput
4
4 7
2 2 8 10
3 6
3 3 9
2 3
3 10
1 5
2

3
2
3
1


Explanation of test case $1$:

Starting of day $1$: $h = [2,2,8,10]$, $x = 7$, $y = 1$

1.      Select $4th$ monster, decrease its health by $x=7$. $h = [2,2,8,3]$.

2.      Decrease health of each monster by $y=1$, excluding the $4th$ monster. $h = [1,1,7,3]$.

3.      $x = 8$

4.      $y = 2$

Starting of day $2$: $h = [1,1,7,3]$, $x = 8$, $y = 2$

1.      Select $3rd$ monster. $h = [1,1, -1,3]$.

2.      Decrease health of each monster by $y=2$, excluding the $3rd$ monster. $h = [-1, -1, -1,1]$.

3.      $x = 9$

4.      $y = 3$

Starting of day $3$: $h = [-1, -1, -1,1]$, $x = 9$, $y = 3$

1.      Select $1st$ monster $h = [-10, -1, -1,1]$.

2.      Decrease health of each monster by $y=3$, excluding the $1st$ monster. $h = [-10, -4, -4, -2]$.

3.      $x = 10$

4.      $y = 4$

All the monsters are dead after $3$ days.

### Statistics

35% Solution Ratio

s_semicolonEarliest, 2M ago

s_semicolonFastest, 0.0s

s_semicolonLightest, 1.7 MB

Zobayer_AbedinShortest, 755B