BILLI - Billi and Kaddu
Bubbleworld is in trouble and our wonderwoman, Billi needs to rescue the prince so as to save the kingdom from the wrath of the monster Kaddu. To do this, she needs to choose K words from a pot of M words she stole from Kaddu, and convert them to magical words, which she would use as a spell to break into the prison. She already knows N magical words.
The conversion of a stolen word to magical word requires the following operations :
1) Remove a character from the end of the word, which incurs a cost of A coins
2) Add a character to the end, which incurs a cost of B coins.
Help Billi save the kingdom by minimizing the cost required to convert exactly K stolen words to magical words.
First line of every test file contains the number of test cases, T.
For each test case, first line contains 5 integers : A, B, K, N, M
The next N lines contain a string each, denoting the set of magical words known to Billi.
The next M lines contain a string each, denoting the set of words stolen from Kaddu.
T <= 20
1 <= N <= 10000
1 <= M <= 10000
1 <= K <= M
1 <= A,B <= 1000
Length of each string <= 100
The strings consist of only lowercase characters.
For each test case, print the minimum cost for the task in a single line.
2 2 3 1 1 1 abc bca 2 3 2 5 4 harry potter abcde qqwweerr ab abc abcd qqwwweer putter