Nowadays, our senior is typewriting an article for her graduation. But as you know our senior is foolish sometimes, so she needs your help. You can assume senior’s article is a string, and senior’s typewriter provides two operations to typewrite it:
1) Assume you have typewritten a string s, then you can add a character after s, and the cost of adding each character is given to you.
2) Assume you have typewritten a string s, you can select a substring of s and copy it, then you can paste it after s once. The cost to select a character is A，and the cost to copy and paste a string are all equal B.
Now, you should help senior to typewrite the article by using the minimum cost, can you help her?
In the first line there is an integer T($1 \leq T \leq 100$), indicating the number of test cases.
For each test case:
The first line includes a string s ($1 \leq |s| \leq 10^5$) composed by lowercase letters, indicating the article senior want to typewrite.
The second line includes 26 integers, indicating the cost to add character ‘a’, ‘b’, ‘c’…, and so on.
The third line includes two integers A and B.
All the integers in the input are in the range of $[1, 10^9]$. It is guaranteed that the total length of s doesn't exceed $1.2 \times 10^6$.
For each test case:
Please output “Case #k: answer”(without quotes) one line, where k means the case number count from 1, and the answer is the minimum cost to typewrite the article.