Today is Naruto’s birthday. To celebrate his birthday he and his friends are at Ichimaru’s ramen shop. Naruto has N friends. Each of them wants some number of ramen as birthday treat from Naruto. Let’s index his friends from 1 to N. The i-th of them wants Ai bowls of ramen. The price of each bowl is D dollars. Naruto has only K dollars. Sometimes it’s not enough and when he has less dollars than he needs to buy ramen for all of his friends, he borrows some dollar from Iruka Sensei.

Now given all this information you have to calculate the minimum amount of money Naruto needs to borrow from Iruka Sensei to buy ramen for all of his friends.

Input

The input set starts with a single line integer T (1 <= T <= 50) the number of test cases. T cases follow. Each case starts with an integer N (0 <= N <= 1000) denoting the number of Naruto's friends. The second line of each case contains N space separated integers Ai (0 <= Ai <= 100000) denoting the number of bowls the i-th friend wants. The third line contains two integers K (0 <= k <= 10^9) denoting the amount of money Naruto has and D (0 <= D <= 1000), the price of each bowl.

Output

For each test case output one line “Case X: ” without the quotes where X is the case number starting from 1 and one integer, the minimum amount of money Naruto needs to borrow.

Example

Input:
2
3
1 2 3
5 1
2
2 2
4 2

Output:
Case 1: 1
Case 2: 4