Limits
6s, 512 MB

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 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.

For each case, print the case number and maximum point Bojo can get.

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 |

Login to submit.

0%
Solution Ratio

Toph uses cookies. By continuing you agree to our Cookie Policy.