You are an alchemist tasked with brewing a potion using three magical ingredients: Amber ~(1)~, Beryl ~(2)~, and Crystal ~(3)~. Your available ingredients are represented by a string ~S~ containing only the characters ~1~, ~2~, and ~3~. However, this potion is dangerously potent, and your goal is to arrange the ingredients in a sequence that minimizes its total potency to make it safe for use. The potency is determined by the sum of magical reactions between consecutive pairs of ingredients, as recorded in an ancient recipe book. Each pair (e.g., 12 or 23) has a potency value, and the book specifies that reversing a pair (e.g., 12 to 21) results in the same potency. Find the arrangement of ingredients that yields the minimum possible potency.

Input

• The first line contains the string ~S~ (with a length ~|S| ≤ 300~).
• The second line contains an integer ~n~, the number of reaction entries in the recipe book.
• Each of the following ~n~ lines contains a two-character ingredient pair and an integer, representing the potency value of that pair.

Output

• The minimum potency achievable by arranging all ingredients from ~S~ into a sequence.

Sample Input

231123
3
12 2
23 4
13 3

Sample Output

5

Explanation

• One arrangement of the ingredients that yields the minimum potency is 221133. The total potency is calculated by summing the reactions of consecutive pairs: ~22 + 21 + 11 + 13+ 33 = 0 + 2 + 0 + 3 + 0 = 5~.