The newly opened casino offered an original game.
At the beginning of the game, the croupier places several chips of different colors in a row. In addition, he announces which sequences of chips the player can take during the game. Next, the player takes one of the pre-announced sequences of chips arranged in a row. After that, the croupier moves the remaining chips, removing the gap. Then the player again takes one of the declared sequences for himself, and so on. The game continues as long as the player can collect chips.
Consider an example. Let there be a row of rrrgggbbb chips on the table, and the croupier announces the sequences rg and gb. The player, for example, can pick up the rg chips lying in the third and fourth places from the left. After that, the croupier will move the chips, and a row of rrggbbb will appear on the table. Taking the rg chips twice more, the player will ensure that the bbb chips remain on the table and the game will end, since the player has nothing more to take from the table. The player could have acted differently — on the second and third moves, take not sequences rg, but sequences gb. Then there would be rrb chips on the table. Likewise, the player could have the rrr or rbb rows at the end.
After the end of the game, the player exchanges the received chips for money. The price of a chip depends on its color.
It is required to write a program that determines the maximum amount that a player can receive.
Input
The first line of the input contains the number K (1 ≤ K ≤ 26) — the number of chip colors. Each of the next K lines starts with a lowercase latin letter denoting a color. Further on the same line, space-separated integer Xi (1 ≤ X
i ≤ 150, i = 1..K) — the price of the corresponding color chip.
The (K+2)-th line describes a row of chips lying on the table at the beginning of the game. The row is given by L lowercase Latin letters (1 ≤ L ≤ 150), which indicate the colors of the chips in the row.
The next line contains the number N(1 ≤ N ≤ 150) — the number of sequences that were announced by the croupier. The next N lines contain these sequences. It is guaranteed that the sum of the lengths of these N strings does not exceed 150 characters, and they are all non-empty.
Imprint
Print a single integer — the maximum amount of money a player can receive.
Examples
| # |
Input |
Output |
| 1 |
3
v3
l 1
u 2
luvu
3
vul
uuu |
6 |