Stackmatch is a very popular game of Matland. In this game, they uses C types of coins and a stack. Coins are numbered from 1 to C. In each move, they put a coin(any of the C types) on top of the stack. If the topmost K coins are of the same type, then topmost K coins disappear. All other(If any) coins of the stack remain as they were. The game has an interesting property, before starting the game they fixed the exact number of moves M they will play. To finish the game after M moves the stack must be empty.
CDFF is a famous game company of Matland. They have made a robot named Bingo who can calculate the number of way to finish a Stackmatch game after exactly M moves. Two ways are different if there exists an i such that ith pushed coin is different. The answer could be very large. But Bingo can’t handle large numbers. His answer is always modulo W.
CDFF has announced a game. To win the game you need to be lucky and intelligent both. To select the winner, N credit cards are given to each participant. Cards are numbered from 1 to N. The ith card has a hidden number Di. After scratching, candidate can see the hidden number. When a candidate put the card on one of the hand of Bingo it recharge the card by exactly Xi gems. Where Xi is the number of way to finish a Stackmatch game after exactly Di moves modulo W. Initially balance of all cards are zero (no gem). Remember C and W are fixed for all cards of a game.
CDFF has published a predefined point list P of W+1 elements. They give Pi points for a card having i gem(s) in the time of submission. Here Pi is the ith element of P. So total point of a candidate is the sum of all points for all cards. Maximum capacity of a card is W(a card cannot be charged by more than W gems).
To make the game more interesting they placed some Gem Transfer Machine, since everybody wants to maximize his points. Gem Transfer Machine is a machine having two slots for two cards, slot A and slot B. When a candidate puts two cards in two slots then gems from the card of slot A transfers into the card of slot B until either card of slot A becomes empty or card of slot B becomes full, whichever happens earlier. Candidates can use this machines as many times they want and also they can use a card multiple times for transferring jems before submitting cards to CDFF. After submission CDFF takes all cards from each candidate.
Bojo is a candidate of the tournament. As a friend of Bojo, help him to maximize his point.
Input
Input starts with number of test cases, T (T ≤ 30) followed by a blank line.
Each test case begins with four integers, N(1 ≤ N ≤ 12), C(1 ≤ C ≤ 6), K(2 ≤ K ≤ 15) and W(2 ≤ W ≤ 100). Next line contains N space separated integers Di (1 ≤ Di ≤ 1000) denoting hidden number of ith card. Next line contains W+1 space separated integers Pi (1 ≤ Pi ≤ 1000) denoting points for a card having i(0 ≤ i ≤ W) gem(s).
There will be a blank line preceding every test case.
Output
For each case, print the case number and maximum point Bojo can get.
Sample
| Input | Output |
|---|---|
2 3 4 2 3 2 4 3 20 1 100 5 3 4 2 3 2 4 3 20 10 1 5 | Case 1: 140 Case 2: 41 |
