Casino

A newly opened casino offers an original game. At the start, the dealer lays out several chips of different colors in a row and announces which sequences of adjacent chips the player may take. The player takes one of the announced sequences, and then the dealer shifts the remaining chips to close the gap. The player then takes another announced sequence, and so on. The game continues as long as the player can take chips. For example, suppose the row is rrrgggbbb and the dealer announces rg and gb. The player may take the rg at the third and fourth positions from the left. Then the dealer shifts the chips and the row becomes rrggbbb. Taking rg two more times leaves bbb, and the game ends because the player has nothing left to take. The player could instead take gb on the second and third moves, which leaves rrb. Similarly, the player could end with rrr or rbb. After the game, the player exchanges the collected chips for money. The price of a chip depends on its color.

The first line contains the number of colors K (1 to 26). Each of the next K lines starts with a lowercase Latin letter for a color, followed by a space and an integer Xi (1 to 150), the price of a chip of that color. The line K+2 gives the row of chips on the table at the start of the game, written as L lowercase Latin letters (1 to 150). The next line contains N (1 to 150), the number of sequences announced by the dealer. The following N lines contain these sequences. The total length of these N lines does not exceed 150 characters, and every sequence is non-empty.

Print a single integer, the maximum amount of money the player can receive.