Cheapest Palindrome

Interview

Time limit1sMemory limit128 MB

Summary

Given a string and per-letter insertion and deletion costs, find the minimum cost to turn it into a palindrome by adding or removing characters anywhere.

Level: Medium6 of 10
Topics: Dynamic programming, String, Array, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples5

Example 1

Input

3 4
abcb
a 1000 1100
b 350 700
c 200 800

Expected output

Example 2

Input

3 5
abcba
a 1000 1100
b 350 700
c 200 800

Expected output

Example 3
Input
```
1 1
a
a 5 7
```
Expected output
```
0
```
Example 4
Input
```
1 2
aa
a 5 7
```
Expected output
```
0
```
Example 5
Input
```
2 2
ab
a 100 200
b 50 300
```
Expected output
```
50
```