You are given the cost of changing \(M\) pairs of lowercase characters \(x\) to \(y\). You are also given a string \(S\).

You can change a character in string \(S\) to another lowercase character by spending the cost you were given earlier. Determine the minimum cost that is required to make \(S\) a palindrome.

You can assume that it is always possible to make S a palindrome.

Notes

• Each pair of characters is there at most 1 time in the input.
• A string \(S\) is called a palindrome if it reads the same if it is read backwards. For example, 'radar', 'madam', 'racecar' are palindromes whereas 'pizza' is not.

Input format

• The first line contains string \(S\).
• The next line contains integer \(M\).
• The next \(M\) lines each contain a pair of lowercase characters \(x\), \(y\), and cost \(c\). You can change character \(x\) to character \(y\) or vise versa spending cost \(c\).

Output format

Print the minimum cost that is required to make \(S\) a palindrome.

Constraints

\(1 \le |S| \le 10^5\)

\(0 \le M \le 325\)

\(1 \le C_i \le 10^8\) where \(C_i\) is the cost of changing the \(i^{th}\) pair of characters