Matt Laundro is about to engage in his favourite activity - doing laundry! He's brought L indistinguishable loads of laundry to his local laundromat, which has N washing machines and M dryers. The ith washing machine takes Wi minutes to wash one load of laundry, and each dryer takes D minutes to dry a load of laundry. At any point in time, each machine may only be processing at most one load of laundry.
As one might expect, Matt wants to wash and then dry each of his L loads of laundry. Each load of laundry will go through the following steps in order:
A non-negative amount of time after Matt arrives at the laundromat, Matt places the load in an unoccupied washing machine i
Wi minutes later, he removes the load from the washing machine, placing it in a temporary holding basket (which has unlimited space)
A non-negative amount of time later, he places the load in an unoccupied dryer
D minutes later, he removes the load from the dryer
Matt can instantaneously add laundry to or remove laundry from a machine. Help Matt minimize the amount of time (in minutes after he arrives at the laundromat) after which he can be done drying all L loads of laundry!
Input begins with an integer T, the number of times Matt goes to the laundromat. For each trip to the laundromat, there is first a line containing the space-separated integers L, N, M, and D in that order. After that is a line containing N space-separated integers, the ith of which is Wi.
For the ith trip, print a line containing "Case #i: " followed by the minimum time it will take Matt to finish his laundry.
1 ≤ T ≤ 50
1 ≤ L ≤ 1,000,000
1 ≤ N ≤ 100,000
1 ≤ M ≤ 1,000,000,000
1 ≤ D ≤ 1,000,000,000
1 ≤ Wi ≤ 1,000,000,000
Explanation of Sample
In the first case, Matt has just one load of laundry. He washes it for 1200 minutes, and dries it for 34 minutes. In the second case, Matt uses the 1-minute washer for both loads of laundry. The second load finishes at the 2-minute mark, so it finishes drying at the 12-minute mark.
Code: Select all
5 1 1 1 34 1200 2 3 2 10 100 10 1 3 3 3 3 1 2 3 4 2 2 7 5 8 999 1 999 6 3
Code: Select all
Case #1: 1234 Case #2: 12 Case #3: 5 Case #4: 22 Case #5: 3003