You all know about my friend Hippo. Hippo and its other hippopotamus friends are starting a circus. They have been practicing a lot, and they are getting better at the show. I have seen their show several times and I personally think they are really good. So I encouraged them to show in public. And after a lot of arguing and convincing they finally agreed. So are they are getting ready for their big showdown. Everything is prepared. The performers are working day and night to perfect everything. The tent is almost ready. In a word everything is having the final touch. In the night before the show the hippopotamuses started to budget the time and encountered a big problem. They were planning for a big entrance where every hippopotamus will enter through the gate and take a bow to the audience. But this is taking too much time. So to shorten this they devised a plan — “One hippo will ride another one”. The balances of the hippopotamuses are not so good yet. So a hippo can take only another hippo over it, not more than that. There is another problem, if a hippo carries another hippo, it slows the speed of the hippo. So to help them with the problem they wish your help. Given a door with height H, and N hippopotamuses with height hi (height of the i-th hippo, 1 ≤ i ≤ N), you need to find the minimum time so that every hippo can enter the door and bow. A hippo can only enter the door if its height is less than the height of the door. If a hippo is carrying another hippo, then the summation of their heights must be less than the door’s height. A hippo while walking alone, takes Ta time to enter the door and bow. A hippo while carrying another hippo, takes Td time to enter and bow. Input First line of input will contain an integer, C (1 ≤ C ≤ 10), the number of test cases. Then C cases will follow. First line of each case is four integers, N, H, Ta, and Td. Next line contains N integers, the height of the hippopotamuses. Here, 1 ≤ N ≤ 100000 and 0 ≤ Ta < Td ≤ 10000. All the heights will be less than 100. Heights of all the hippopotamuses will be less than the H. Output Foreachcaseoutputoneline.‘CaseX: M’(withoutthequotes),whereXisthecasenumberstarting from 1 and M is minimum time needed. Check sample input and output for details. Explanation: In the first case, all the hippo walks alone that’s why each take 2 seconds and in a total of 6 seconds. But in the second case, if the first hippo carries the third hippo (3 + 2 < 6) then it takes 3 seconds and the other hippo takes 2 seconds.
2/2 Sample Input 2 3523 342 3623 342 Sample Output Case 1: 6 Case 2: 5