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