题目描述

小瑶在一家珠宝商店看到一些珍珠手链，不同颜色的珍珠有不同的价值，对于思维异常的小瑶来说，他并不关注的整条手链价值是多少，而关注若是从手链中取出连续一段，取出的这段可能有多种不同颜色的珍珠，但至多有一种颜色珍珠可以有多个，如：RRWWW这一段就不可以，因为R和W这两种颜色的珍珠都不止1个，而RWWW或RRW是可以的。

现在小瑶想知道，对于给定长度的手链，他所关注的所有连续段中，价值和最大是多少？

注意：手链是环形的。

输入格式

第一行两个数n，表示手链的长度。

第二行n个用大写字母组成的串，表示手链上的珍珠。

第三行26个数，分别表示A~Z这26种颜色珍珠的价值。

注：并非一条手链会有全部颜色的珍珠。

输出格式

一行一个数，表示答案。

样例

6
RRWWWR
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

87

解释#1

R、W、RR、WW、RW、WR、RRR、RRW、RWW、WWW、WWR、WRR、RRRW、RWWW、WRRR、WWWR都是小瑶所关注的，其中RWWW与WWWR的价值最大，即为18+23*3=87。

14
HBLBVRDFVQEHHJ
78 562 780 534 237 363 934 283 495 18 287 488 735 440 504 116 141 313 906 163 95 818 445 453 210 209

4557

解释#2

价值最大的一段为LBVRDFVQEH，除了V是2个，其它都是一个。

数据范围

对于20%的数据，n≤100。

对于另外20%的数据，保证手链的珍珠是一种颜色。

对于另外20%的数据，保证手链的珍珠只有两种颜色。

对于另外10%的数据，保证数据是随机生成的。

对于100%的数据，n≤10^6，1≤每种珍珠的价值≤10^4。

提示：非官方数据