TRSPACE - True Space
In some file systems, the disk space used by a file is not always equal to the file's size. This is because the disk is divided into clusters of equal size, and each cluster can only be used by a single file. For example, if the cluster size is 512 bytes, and we have a file of size 600 bytes, it would have to be stored in two clusters. Those two clusters cannot be shared with any other files, so the file ends up using 1024 bytes of disk space.
Note that we don't need any clusters for a file of size 0.
Given N single files and the cluster size, you have to print the total disk space used by the given files.
Input
The first line of input will contain T denoting the number of test cases. The first line of each test case contains two integers N, denoting the number of files and S, denoting the cluster size of the file system. The second line of each test case contains N integers ai (1 <= i <= N) denoting the size of the ith file.
Constraints:
1 <= T <= 1000
1 <= N <= 100
1 <= S <= 1048576
0 <= ai <= 10^9
Output
For each test case print a single line containing “Case X: S” without the quotes, where X is the case number and S is the total disk space used by the given files.
Example
Input: 2 1 512 600 4 32768 16 32 128 128 Output: Case 1: 1024 Case 2: 131072
Added by: | imranziad |
Date: | 2016-11-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |