题目描述

你正在玩一个发生在二维平面上的寻宝电子游戏。

你有一个长度为 $m$、仅由 R、U 和 ? 组成的字符串 $s$。首先，你需要将 $s$ 中每个 ? 替换为 R 或 U。

替换所有 ? 后，你从 $(0,0)$ 出发，按照 $s$ 进行 $m$ 次移动。设你当前的位置为 $(x,y)$。在第 $i$ 次移动中，如果 $s$ 的第 $i$ 个字符为 R，则你的下一个位置为 $(x+1,y)$；如果为 U，则下一个位置为 $(x,y+1)$。

平面上有 $n$ 个宝箱。第 $j$ 个宝箱位于 $(a_j,b_j)$，如果你到达这个位置，就可以打开该宝箱，获得 $c_j$ 枚金币。同一个点上可能有多个宝箱。如果你到达这样的点，可以打开该处的所有宝箱，获得其中的全部金币。

如果你以最优方式替换 $s$ 中的每个 ?，最多能获得多少枚金币？

输入格式

输入包含一组测试数据，格式如下。

m n
s
a_1 b_1 c_1
a_2 b_2 c_2
...
a_n b_n c_n

第一行包含两个整数 $m,n$。$m$ 表示游戏中的总移动次数（$1\le m\le3\times10^5$），$n$ 表示宝箱的数量（$1\le n\le3\times10^5$）。

第二行包含一个长度为 $m$ 的字符串 $s$，其中每个字符均为 R、U 或 ?。

接下来 $n$ 行，每行包含三个整数 $a_j,b_j,c_j$。$(a_j,b_j)$ 是第 $j$ 个宝箱的位置（$a_j\ge0$，$b_j\ge0$，$1\le a_j+b_j\le m$）。$c_j$ 是该宝箱中的金币数量（$1\le c_j\le10^9$）。

输出格式

输出你最多能获得的金币数量。

8 5
R?UU?U?R
1 2 3
2 3 5
1 6 1
3 5 4
5 3 10

12

10 2
RRRRUUUURR
5 0 10
0 1 8

0

20 15
?RU?R?????U?R?UR???U
1 7 19
16 4 13
1 0 15
8 3 20
7 8 18
2 10 17
5 9 15
14 6 16
0 1 6
11 1 19
10 2 14
12 3 11
4 11 18
2 3 16
2 16 11

57

提示

在样例 1 中，一种最优的替换方式会得到字符串 RUUURUUR。按照该字符串移动，你可以打开第一个、第二个和第四个宝箱，共获得 $12$ 枚金币。