Palindromic changes
/

## Algorithms, Dynamic Programming, Floyd Warshall, Graphs, Shortest Path Algorithms, String

Problem
Editorial
Analytics

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

SAMPLE INPUT
mat
2
m t 10
a m 5
SAMPLE OUTPUT
10
Explanation

To convert the string "mat"  into a palindrome we can convert 'm' to 't' thus incurring a cost 10 and getting the string "tat" which is a palindrome. You can check that this is the minimum possible cost.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...