Problem Description

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

Input Format

The input consists of a single test case of the following format.

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 Format

Output the maximum number of coins you can collect.

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

Hint

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.