All Tracks Algorithms Graphs Shortest Path Algorithms Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?