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

**[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.

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$.

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

Input | Output |
---|---|

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. |

35% Solution Ratio

s_semicolonEarliest,

s_semicolonFastest, 0.0s

s_semicolonLightest, 1.7 MB

Zobayer_AbedinShortest, 755B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.