UOJ Logo

NOI.AC

1S 666MB

#18. B

统计

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

下载

样例数据下载