Cheapest Palindrome

Farmer John has installed an automated system to keep track of his cows. Each cow wears an electronic ID tag that the system reads as the cow passes a scanner. Every ID tag holds a single string of length $M$ ($1 \le M \le 2000$) whose characters are drawn from an alphabet of $N$ ($1 \le N \le 26$) lower-case roman letters.

Being mischievous, the cows sometimes try to fool the system by walking backwards. A cow whose ID is abcba reads the same in either direction, but a cow whose ID is abcb may register as two different strings (abcb and bcba).

John wants to edit each ID tag so that it reads the same no matter which way the cow walks, i.e. so that the tag is a palindrome (reads identically forwards and backwards). For instance, abcb can be turned into abcba by adding an a at the end, into bcbabcb by adding bcb at the front, or into bcb by deleting the a. Characters may be inserted or deleted at any position, and the resulting string may be longer or shorter than the original.

Because the tags are electronic, each insertion or deletion of a character costs a certain amount ($0 \le \text{cost} \le 10000$) that depends on which character is added or removed. Given a cow's ID tag and the cost of inserting and deleting each letter of the alphabet, find the minimum total cost to make the tag a palindrome. An empty tag is considered to read the same forwards and backwards. Only letters that have an associated cost may be added to the string.

• Line 1: Two space-separated integers $N$ and $M$.
• Line 2: Exactly $M$ characters that make up the initial ID string.
• Lines 3 to $N+2$: Each line contains a character of the alphabet followed by two integers, the cost of adding and the cost of deleting that character, all space-separated.

• Line 1: A single integer, the minimum cost to make the ID tag a palindrome.