BANKQUE - Waiting Queue

no tags 

 

 

It is the beginning of the day at a bank, and a crowd of N clients is already waiting for the entrance door to open.
Once the bank opens, no more clients arrive, and E employees begin serving the clients. An emplyee 
takes T minutes to serve each client. How long each client has already been waiting at the moment when the bank door opens
is also given.Your have to determine the best way to arrange the clients into E queues,
so that the waiting time of the client who waits longest is minimized.
The waiting time of a client is the sum of the time the client waited outside before the bank opened,
the time the client waited in a queue once the bank opened until the service began, and the service time of the client.
It is the beginning of the day at a bank, and a crowd of N clients is already waiting for the entrance door to open. Once the bank opens, no more clients arrive, and E employees begin serving the clients. An employee takes T minutes to serve each client. How long each client has already been waiting at the moment when the bank door opens is also given.Your have to determine the best way to arrange the clients into E queues so that the waiting time of the client who waits longest is minimized.The waiting time of a client is the sum of the time the client waited outside before the bank opened, the time the client waited in a queue once the bank opened until the service began, and the service time of the client.

Input

First line contains k (the number of test cases). Then k test cases follows. First line of each test case contains N, E and T as described above. Next line contains N integers t1, t2, ..tn, ith of which is the waiting time of ith client before the opening of door.

Constraints:  1<=k<=25,  1<=N<=50,  1<=E<=50,  1<=T<=100,  0<=ti<=100

Output

For each test case print in a seperate line the minimum waiting time for the client who waits the longest.

Example

Input:
3
2 1 10
1 2
1 50 50
10
5 3 10
2 4 6 3 5

Output:
21
60
23


Added by:Mahesh Chandra Sharma
Date:2011-01-09
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Based on a topcoder problem