## BANKQUE - Waiting Queue

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 5Output: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 |