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.

Input

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.

Constraints

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.

Output

For each test case, print the minimum cost for the task in a single line.

Example

Input

2
2 3 1 1 1
abc
bca
2 3 2 5 4
harry
potter
abcde
qqwweerr
ab
abc
abcd
qqwwweer
putter

Output

15
5