A :: Anagrams

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Anagrams is word game that involves rearranging letter tiles to form words. Each piece has a lower or upper Latin letter on it.

Little Hamed has received an Anagrams puzzle for his birthday. But he does not know the rules of the game. So he simply arranges tiles beside each other to form new words and sentences. Little Hamed arranged the words to form a sentence. He was so happy because he managed to use all the pieces of letters he got. But after a more careful look, he thought the sentence is not that beautiful. He decided to rearrange it to make a more beautiful sentence. This time he does not want to necessarily use all the pieces. The new puzzle Little Hamed wants to form, lack some letters and some letters are extra.

There is a toy shop in the vicinity that sells or exchanges letter tiles. Little Hamed can exchange a tile for a tile with the same letter but different case for C Tomans. He can exchange a tile with a tile of any letter and any case for S Tomans. He can also buy a new tile for B Tomans. The prices are reasonable relative to each, i.e. C < S < B.

Now, given the first puzzle Little Hamed has arranged, help him obtain all the tiles that are required to form his new puzzle with minimum possible cost.

Input

First line of input contains a single integer t (t ≤ 100), the number of tests that follow. The first line of each test contains three space-separated integers C, S, B (1 ≤ C < S < B ≤ 10⁶), the cost of changing case of a tile, exchange a tile with a different tile and buying a new tile, respectively.

Next two lines describe the puzzle that Little Hamed has arranged and the new puzzle he wants to form. Each puzzle contains only lower and upper Latin letters and space character. Length of each puzzle does not exceed 100. There will be no leading or trailing spaces in description of a puzzle and two words in a puzzle are separated with a single space. Note that space is not puzzle tile and is only used to separate different words of the puzzle.

Output

For each test you should output a single line, the minimum cost to prepare all the tiles required two form the second puzzle.

Sample Input

3
1 100 10000
write SaMpLe
is not sImPlE
1 100 10000
Happy PMP
Zart PMP
1 100 10000
Last war of PMP
Reincarnation of PMP

Sample Output

405
300
60300

Submit

Source: 4th Kashan University's ACM Contest