Minimum Cost Palindromic ID Conversion

Farmer John wants to ensure that each cow's electronic ID tag reads the same whether the cow walks forwards or backwards. Each tag is a string of length \(M\) (\(1 \le M \le 2000\)) drawn from an alphabet of \(N\) (\(1 \le N \le 26\)) lower-case letters. Since cows might spoof the system by walking backwards, FJ wants to modify each ID so that it becomes palindromic (i.e. reads the same forward and backward).

You can modify the ID tag by inserting or deleting characters at any position; note that the resulting string may be longer or shorter than the original. An empty ID tag is considered palindromic. Each insertion or deletion has an associated cost that depends on the specific character. Only letters with provided costs may be inserted.

Given the initial ID tag and the associated insertion and deletion costs for each letter, determine the minimum cost required to transform the ID tag into a palindrome.

inputFormat

The input begins with a line containing two integers \(M\) and \(N\), where \(M\) is the length of the ID tag and \(N\) is the number of distinct characters with associated costs.

The second line contains a string of length \(M\) representing the cow's ID tag.

Each of the next \(N\) lines contains a character followed by two integers: the cost to insert that character and the cost to delete that character. All cost values are between 0 and 10,000 (inclusive).

It is guaranteed that the string contains only the characters that have corresponding cost information.

outputFormat

Output a single integer — the minimum cost to modify the ID tag so that it reads the same forwards and backwards.

sample

4 3
abcb
a 3 2
b 4 3
c 5 3

2