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