Aakash has invented a new kind of Web Browser known as an Integer Browser.
It downloads files in integer speeds.
The way it works is as follows:
Suppose there are 12 files downloading with an internet speed of 100 kb/s. Then the speed of download for each file is the floor of 100/12 i.e. 8 kb/s.
Now suppose we have a file of 27 kb downloading at a speed of 8 kb/s. The time taken for the download of this file is the ceiling of 27/8 which is 4 seconds.
Now, let’s assume that we have 8 files of different sizes, and an internet speed of 23 kb/s.
The file sizes are 84, 53, 96, 101, 53, 87, 89, and 42 KB respectively.
How long will it take for the files to download? Note that once a file has finished downloading,
then the speed of download increases for the other files.
The calculation is outlined in the diagram below:
enter image description here
First, the speed of each file downloading is 2 kb/s. The download happens parallely. It takes 21 seconds for the file of size 42 KB to be downloaded.
And 42 KB of each of the rest of the files have been downloaded. Now, only 7 files are left to be downloaded.
This time the download speed is 3 kb/s.
It takes 4 seconds to download the remaining 11 kb of two of the files. (Remember point 2.)
This process is repeated until all files are downloaded. As you can see, it takes a total of 37 seconds for all files to be downloaded.
The first line of input consists of an integer t. This is the number of test cases.
For each test case, the first line of input contains two space separated integers n and s.
Here n is the number of files and s is the internet speed (in KB/s). Then the next line contains n space separated integers which are the sizes (in KB) of the n files.
Here n will always be less than s, because, if not, then s/n will be 0 and no files could be downloaded.
For each test case, output a single integer which is the time taken by the Integer Browser to download all the files.
0 < t <= 1000 (This is the number of test cases)
0 < n <= 10000 (This is the number of files)
0 < s <= 30000 (This is the speed of internet in kb/s)
0 < Xi < 100000 (This is the size of each files in kb)
84 53 96 101 53 87 89 42
79 64 23 53 47 103 100 109 68
30 24 26 25 100 98 78