题目描述

小珅准备了 $n$ 颗美味的糖果来卖给小泽。每天小珅只会售出两颗糖果。这些糖果有以下这些有趣的特性：

（1）糖果按照 $1\sim n$ 编号，它们被排成一列放在一个很长的盒子里。盒子的末端有开口，可以看到最末端的 $3$ 颗糖果，小珅每天可以从最末端的 $3$ 颗糖果中任意取出 $2$ 颗销售。如果只剩 $2$ 颗糖果，那么就出售这 $2$ 颗。只剩 $1$ 颗糖果不能单独出售。

（2）糖果有不同的颜色，用大小写字母表示。每种颜色有自己的特征值，当两颗糖果搭配出售时，售价取决于颜色组合。如果两个特征值为 $x,y$ 的糖果在同一天出售，小珅当天的收入就等于 $x^y+y^x$ 除以 $257$ 的余数。

给出每颗糖果的颜色，和每种颜色的特征值，请求出小珅最多可以获得多少收入。

输入格式

第一行输入两个整数 $n,k$，分别表示糖果的数量和颜色的种类数。

第二行输入一个长度为 $n$ 的字符串 $s$，其中 $s_i$ 表示第 $i+1$ 颗糖果的颜色。

接下来 $k$ 行，每行输入一个字符 $c$ 和一个正整数 $e$，分别表示一种颜色和该颜色的特征值。

输出格式

输出一个整数，表示小珅最多可以获得的收入。

6 2
ABAABB
A 2
B 3

79

9 3
CACBBACCA
A 8
B 6
C 5

476

18 6
bbbBaaaDaaaBCbDCAA
A 2
B 4
C 8
D 4
a 6
b 3

1419

49 10
LfHwwHkLxukwxfLLkfLkOkMkWuwkkwkxWOMuHxOMkWWLLwHwL
O 4
u 5
k 5
H 6
f 3
M 6
W 7
L 7
w 5
x 3

3577

说明提示

样例 $1$ 中，各种搭配的售价为：AA 的售价是 $8$，AB 的售价是 $17$，BB 的售价是 $54$。第一天从末端的 ABB 中出售 BB，第二天从末端的 BAA 中出售 AB，第三天只剩 AA，出售 AA，总收入为 $54+17+8=79$。

样例 $2$ 中，各种搭配的售价如下：

• AA：$8^8+8^8=33554432\equiv255\pmod{257}$；
• AB：$125$；
• AC：$114$；
• BB：$21$；
• BC：$14$；
• CC：$82$。

第一天从末端的 CCA 中出售 CC，收入 $82$；第二天从末端的 BAA 中出售 AA，收入 $255$；第三天从末端的 CBB 中出售 BC，收入 $14$；第四天从末端的 CAB 中出售 AB，收入 $125$；最后剩余一颗糖果，总收入为 $82+255+14+125=476$。

数据范围

对于 $100\%$ 的数据：$2\le n\le2\times10^5$，$1\le k\le52$，字符串 $s$ 的长度为 $n$，只包含大小写英文字母；$c$ 是大小写英文字母；$1\le e\le255$。

6 2
ABAABB
A 2
B 3

79

9 3
CACBBACCA
A 8
B 6
C 5

476