Lyra 是一个灵巧的女孩子，她特别喜欢玩一种叫“石头剪刀布”的游戏，在这个游戏中，每回合双方同时打出一种手势，为石头(r)，剪刀(s)，布(p)之一，规定石头打败剪刀，剪刀打败布，布打败石头，若手势一样则视为平局。
虽然 Lyra 是一个灵巧的女孩子，她发现她依然赢不了 Evan，潜心研究多日 Evan 的策略后，发现在第二天的 $n$ 轮游戏中，Evan 一定以某种固定策略出手势。
这个固定策略（一个长度为 $n$ 的由 $\texttt{r,s,p}$ 组成的字符串）就藏在 Evan 的电脑里，被 Evan 加密存储。Evan 的加密方式很奇怪，他先选取一个特定的 $d$，然后把整个字符串循环右移 $d$ 个位置。
Lyra 拿到了加密后的策略串，她想在第二天的石头剪刀布比赛中大败 Evan，注意 Lyra 的策略不一定必须是开始前固定的，可以根据前若干回合的结果修正之后的策略。
在这场石头剪刀布大赛中，对于第 $i$ 个回合，获胜可以获得 $w_i$ 分，平局获得 $d_i$ 分，而失败获得 $0$ 分。Lyra 想知道自己采取最优策略的话，最坏情况下至少从这 $n$ 个回合中获得多少分。
输入格式
第一行三个正整数 $n$ 表示回合数。
第二行一个长度为 $n$ 的字符串 $S$ 表示 Evan 的序列的某个轮换。
接下来 $n$ 行每行两个整数 $w_i, d_i$，表示获胜得分，平局得分。
输出格式
一行一个正整数表示 Lyra 至少获得的分数。
样例输入输出
样例输入1
5 rrsrr 3 1 3 1 3 1 3 1 3 1
样例输出1
12
样例输入2
6 rsprsp 3 1 3 1 3 1 3 1 3 1 3 1
样例输出2
15
样例输入3
见 $\texttt{/dexterity/ex_dexterity3.in}$
样例输出3
见 $\texttt{/dexterity/ex_dexterity3.ans}$
注意： 对于所有的样例数据，获胜收益为 $3$，平局收益为 $1$。
数据范围与约定
对于全部数据 $1 \leq n \leq 1 \times 10^5; 0 \leq d_i \leq w_i \leq 10^9$.
Subtask 1[5pts]:
$n \leq 10$.
Subtask 2[14pts]:
$n \leq 16$.
Subtask 3[17pts]:
$n \leq 50$.
Subtask 4[18pts]:
$n \leq 1000$.
Subtask 5[19pts]:
$n \leq 10^5; S$ 随机生成.
Subtask 6[27pts]:
$n \leq 10^5$.
时间限制：$1\texttt{s}$
空间限制：$666\texttt{MB}$
