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}$

下载

样例数据下载