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 nn monsters, and their health point is described by an array hh consisting of nn positive integers. A monster is dead when its health point becomes non-positive (0\le 0).

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

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

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

1.     Harry selects a monster, and deals xx 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 yy damage to each of these monsters.

3.     xx is increased by 11.

4.     yy is increased by 11.

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(1t10000)t (1\le t \le 10000) — the number of test cases.

Each test case consists of two lines. The first line contains two integers nn and xx (1n2×105;2x109)(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 nn integers h1,h2,,hnh_1,h_2,\ldots,h_n  (1hi109)(1 \le h_i \le 10^9) — initial health point of each monster.

It is guaranteed that the sum of nn over all test cases does not exceed 2×1052 \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 11:

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

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

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

3.      x=8x = 8

4.      y=2y = 2

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

1.      Select 3rd3rd monster. h=[1,1,1,3]h = [1,1, -1,3].

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

3.      x=9x = 9

4.      y=3y = 3

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

1.      Select 1st1st monster h=[10,1,1,1]h = [-10, -1, -1,1].

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

3.      x=10x = 10

4.      y=4y = 4

All the monsters are dead after 33 days.


Discussion

Statistics


35% Solution Ratio

s_semicolonEarliest, 2M ago

s_semicolonFastest, 0.0s

s_semicolonLightest, 1.7 MB

Zobayer_AbedinShortest, 755B

Submit

Login to submit

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