#include <iostream>
#include <cstring>

using namespace std;

char s1[ 2010 ], s2[ 2010 ];
int dp[ 2010 ][ 2010 ][ 2 ];
int len, n, all[ 2 ];
int ch[ 150 ][ 2 ];

void reverse( char *s, int len )
{
	
	for ( int i = 0; i < len / 2; ++i )
		swap( s[ i ], s[ len - 1 - i ] );
}


int main()
{
	int i, j, c;
	char buf[ 100 ], *token;
	
	while ( ~scanf( "%d %d", &n, &len ) )
	{
		
		getchar();
		gets( s1 + 1 );
		
		memset( ch, 0, sizeof( ch ) );
		
		for ( i = 0; i < n; ++i )
		{
			gets( buf );
			
			token = strtok( buf, " " );
			c = token[ 0 ];
			token = strtok( NULL, " " );
			ch[ c ][ 0 ] = atoi( token );
			token = strtok( NULL, " " );
			ch[ c ][ 1 ] = atoi( token );
		}
		
		
		all[ 0 ] = all[ 1 ] = 0;
		
		for ( i = 1; i <= len; ++i )
		{
			all[ 0 ] += ch[ s1[ i ] ][ 0 ];
			all[ 1 ] += ch[ s1[ i ]][ 1 ];
		}
		
		for ( i = 0; i <= len; ++i )
		{
			dp[ 0 ][ i ][ 0 ] = dp[ i ][ 0 ][ 0 ] = all[ 0 ];
			dp[ 0 ][ i ][ 1 ] = dp[ i ][ 0 ][ 1 ] = all[ 1 ];
		}
		
		int MIN = min( all[ 0 ], all[ 1 ] );
		for ( i = 1; i <= len; ++i )
		{
			for ( j = 1; j <= len; ++j )
			{
				if ( s1[ i ] == s1[ len + 1 - j ] )
				{
					MIN = min( MIN, dp[ i ][ j ][ 0 ] = dp[ i - 1 ][ j - 1 ][ 0 ] - ch[ s1[ i ] ][ 0 ] );
					MIN = min( MIN, dp[ i ][ j ][ 1 ] = dp[ i - 1 ][ j - 1 ][ 1 ] - ch[ s1[ i ] ][ 1 ] );
					
				}
				else
				{
					dp[ i ][ j ][ 0 ] = min( dp[ i - 1 ][ j ][ 0 ], dp[ i ][ j - 1 ][ 0 ] );
					dp[ i ][ j ][ 1 ] = min( dp[ i - 1 ][ j ][ 1 ], dp[ i ][ j - 1 ][ 1 ] );
				}
			}
		}
		
		printf( "%d\n", MIN );
		
	}
	
	return 0;
}



我自己怎麼測都對

有哪位牛人可以提供測資嗎@@