该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

靶场校准

【题目描述】

小灰灰正在调试一台射击机器人．机器人开始位于数轴的 $0$，按顺序执行一个长度为 $n$ 的指令串．每条指令是以下三种之一：

• L：向左移动一格．
• R：向右移动一格．
• F：向当前所在的坐标射击一次，位置不变．

数轴上有 $m$ 个靶子，坐标互不相同．第 $j$ 个靶子位于 $x_j$，需要至少被命中 $b_j$ 次，才能获得 $w_j$ 分．射击时，如果当前位置有靶子，它的命中次数增加 $1$；否则没有效果．

执行完全部指令后计算总分：每个达到命中次数要求的靶子获得一次对应分数，未达到要求的靶子不得分．同一个靶子不会重复计分．靶子不影响机器人的移动．

执行前，小灰灰可以将至多一条指令改成另外一种指令，也可以不修改．请计算机器人最多能够获得多少分．

【输入描述】

第一行输入两个整数 $n,m$，分别表示指令数量和靶子数量．

第二行输入一个长度为 $n$ 的字符串，只包含 L、R、F．

接下来 $m$ 行，第 $j$ 行输入三个整数 $x_j,b_j,w_j$，分别表示第 $j$ 个靶子的坐标、命中次数要求和分值．

【输出描述】

输出一个整数，表示最多能够获得的分数．

【样例 1】

【样例 1 输入】

5 2
FRFLF
0 3 10
1 1 6

【样例 1 输出】

10

【样例 1 解释】

不修改时，机器人在坐标 $0$ 射击两次、坐标 $1$ 射击一次，得到 $6$ 分．

将第二条指令 R 改成 F，指令串变为 FFFLF．机器人先在坐标 $0$ 连续射击三次，再移动到 $-1$ 射击，得到 $10$ 分．

要获得两个靶子的全部分数，至少需要四次射击和一次移动．原串有三次射击，因此必须将一条移动指令改成 F．修改第二条时不能命中坐标 $1$；修改第四条时，坐标 $0$ 只被命中一次．所以不能获得 $16$ 分．

【样例 2】

【样例 2 输入】

3 1
FFF
0 2 7

【样例 2 输出】

7

【样例 2 解释】

不修改即可得到 $7$ 分．虽然命中了三次，该靶子也只计分一次．

【数据规模与约定】

对于所有数据，$1\le n,m\le2\times10^5$，$-n\le x_j\le n$，$1\le b_j\le n$，$1\le w_j\le10^9$．所有 $x_j$ 两两不同．

本题采用捆绑测试．只有通过一个子任务的全部测试点，才能获得该子任务的分数．

以上限制针对输入的指令串，不限制修改后的指令串．

【下发样例】

• Data/sample1.in 与 Data/sample1.ans：样例 1．
• Data/sample2.in 与 Data/sample2.ans：样例 2．
• Data/sample3.in 与 Data/sample3.ans：满足子任务 1 的限制．
• Data/sample4.in 与 Data/sample4.ans：满足子任务 2 的限制．
• Data/sample5.in 与 Data/sample5.ans：满足子任务 2 的限制．
• Data/sample6.in 与 Data/sample6.ans：满足子任务 3 的限制．
• Data/sample7.in 与 Data/sample7.ans：满足子任务 4 的限制．
• Data/sample8.in 与 Data/sample8.ans：该样例无特殊限制．
• Data/sample9.in 与 Data/sample9.ans：该样例无特殊限制．

点击下载本题选手目录