[[原文:http://acm.pku.edu.cn/JudgeOnline/problem?id=3280]] 
----
''時間制限'':2000ミリ秒
''メモリ制限''65536:KB
&br;

*問題 [#uef33f92]
牛を絶えず監視し続けるのは大変な仕事なので農夫ジョンはこれを自動化しようとあるシステムを導入しました。
ジョンは各牛に一つずつIDタグを与えました。牛がスキャナーの前を通るとIDタグを読み込みます。
タグは長さM(1<=M<=2000)文字でN(1<=N<=26)個(小文字のローマ式アルファベット)のアルファベットからなる文字列です。
牛は意地悪な生き物なので時々後ろ向きに歩いてシステムを欺こうとします。IDが"abcba"の牛はどっちの方向に歩こうと問題はありませんが、"abcb"の牛は２つの異なるID"abcb", "bcba"に読み込まれてしまう可能性があります。

ジョンは牛がどちらの方向に歩いても大丈夫なようにIDを変更したいと考えています。
例えば"abcb"は後ろに"a"を付け足して"abcba"としてIDが回文になるようにすることができます。
ほかにIDを回文にするには先頭に3文字"bcb"を付け足して"bcbabcb"とする、"a"を取り除いて"bcb"にする、などがあります。
文字列の好きな場所に文字を加えるか、除くかしてもともとの文字列より小さいか大きい文字列を作ることができます。

不幸なことにidタグは電気製品ですので、文字を加えたり除いたりするのにはコスト(0<=cost<=10000)がかかります。コストは加える・取り除く文字によって変わります。牛のIDタグが与えられて、そこにアルファベットの文字を加えるか取り除くかしてジョンの所望するIDタグにするために必要となる、最小のコストを求めてください。
空文字列のタグは要件を満たしているものとします。
またコストの存在する文字のみを文字列に加えることができます。

*入力 [#c82ab44b]
1行目:スペースで区切られた2つの整数N,M
2行目:M文字の初期Idタグ
3~N+2行目:各行は空白で区切られた3つの要素:
使用出来る文字、加えるコスト、取り除くコスト

*出力 [#v3fae8d8]
1行:タグを変更する最小コスト

*入力の例 [#ed934c96]
 3 4
 abcb
 a 1000 1100
 b 350 700
 c 200 800

*出力の例 [#v61f2dd1]
 900

*ヒント [#s080ea73]
"a"を後ろに加えて"abcba"とするならコストは1000になります。先頭の"a"を取り除いて"bcb"とするならコストは1100になります。先頭に"bcb"を加えるならコストは350+200+350=900となり、これが最小です。

*出典 [#uc7c7e37]
USACO 2007 Open Gold