P17583 [JAG 2026 Summer Camp #3] Treasure Hunting

You are playing a treasure-hunting video game that takes place on a two-dimensional plane. You have a string $s$ of length $m$ consisting only of `R`, `U`, and `?`. First, you replace each occurrence of `?` in $s$ with either `R` or `U`. After replacing all occurrences of `?`, you start at $(0,0)$ and make $m$ moves according to $s$. Let $(x,y)$ denote your current location. On the $i$-th move, if the $i$-th character of $s$ is `R`, your next location is $(x+1,y)$; if it is `U`, your next location is $(x,y+1)$. There are $n$ treasure boxes on the plane. The $j$-th treasure box is located at $(a_j,b_j)$, and if you reach this location, you can open the box to collect $c_j$ coins. Multiple treasure boxes may be located at the same point. If you reach such a point, you can open all the treasure boxes there and collect the coins from each of them. Find the maximum number of coins you can collect if you optimally replace each occurrence of `?` in $s$.

The input consists of a single test case of the following format. ```text m n s a_1 b_1 c_1 a_2 b_2 c_2 ... a_n b_n c_n ``` The first line contains two integers $m$ and $n$. $m$ is the total number of moves in this game ($1\le m\le3\times10^5$) and $n$ is the number of treasure boxes ($1\le n\le3\times10^5$). The second line contains a string $s$ of length $m$. Each character of $s$ is either `R`, `U`, or `?`. Each of the next $n$ lines contains three integers $a_j$, $b_j$, and $c_j$. $(a_j,b_j)$ is the location of the $j$-th treasure box ($a_j\ge0$, $b_j\ge0$, $1\le a_j+b_j\le m$). $c_j$ is the number of coins in the box ($1\le c_j\le10^9$).

Output the maximum number of coins you can collect.

In Sample Input 1, one optimal replacement results in the string `RUUURUUR`. With this string, you can open the first, second, and fourth treasure boxes and collect $12$ coins.