This problem was asked in online round to my friend.I am not able to get how to approach the problem using which technique, if someone could help me?, Thanks.

Problem:

****Alice has decided to publish X different comic books.****

****For this Purpose , He has Y printing machines and Z binding machines.****

****The ith printing machine takes print[i] minutes to print all pages of a comic book. Each binding machine takes K minutes to bind all the pages of a comic book.**

****At a single point of time ,each machine(a printing or a binding) can process at most the pages of a single comic book.**

****For publishing comic books , these steps have to be followed.**

****1. An unoccupied printing machine i starts printing the pages of a comic book.**

****2. After print[i] minutes , the printed pages are taken out of the ith printing machine.**

****3. After non-negative amount of time , the printed pages of comic book are placed in an unoccupied binding machine.**

****4. After K minutes, the pages are taken out of the binding machine.**

****Assume that the time is negligible for placing the pages into or removing from the machines.**

****You need to help alice , find out the minimum time in order to publish X comics.**

Input:

1.first line consists of the no of testcases.

2.Second line consists of X,Y,Z,K.

3.Y space separted integers which denote the printing time print[i] of ith printing machine.

OUTPUT:

For each test case , print the minimum time to publish all X comics. Constraints:

1<=t<=10

1<=X<=10^6

1<=Y<=10^5

1<=Z<=10^9

1<=K<=10^9

1<=print[i]<=10^9

Sample Test Cases:

input:

3

2 1 1 34

1100

2 3 2 10

10 16 1

3 2 2 5

5 7

output:

2234

12

15