题目描述

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

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

注意：手环是环形的。

输入格式

第一行一个数 $n$，表示手环的长度。

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

第三行 $26$ 个数，分别表示 $A\sim 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 都是 dash 所关注的，其中RWWW与WWWR的价值最大，即为$18+23\times3=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$ 个，其它都是一个。

数据范围

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