P17583 [JAG 2026 Summer Camp #3] Treasure Hunting

你正在玩一个发生在二维平面上的寻宝电子游戏。 你有一个长度为 $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$ 中的每个 `?`，最多能获得多少枚金币？

输入包含一组测试数据，格式如下。 ```text 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$）。

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

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