Problem H: Ghost

Problem

幽霊が一直線上に左から右に$N$人並んでいる。
最初、左から$i$番目の幽霊は$U_i$が'L'ならば左を、'R'ならば右を向いている。

彼らはとても臆病なのでなるべく怖い幽霊を見たくない。

あなたは、各幽霊に対して振り返るように指示をできる。
後ろを振り返るのは怖いので、$i$番目の幽霊が一回振り返ると$A_i$の恐怖度が発生する。
左を向いている幽霊が振り返ると、右を向く。
右を向いている幽霊が振り返ると、左を向く。

$ i < j $ に対して、$i$番目の幽霊が右を向いていて、かつ$j$番目の幽霊が左を向いている場合、$i$番目の幽霊と$j$番目の幽霊は向き合っていると定義する。
以下の制約が$M$個与えられる。
$S_i$番目の幽霊は$T_i$番目の幽霊が怖い。
最終的な状態で、$S_i$番目の幽霊と$T_i$番目の幽霊が向き合っていると$B_i$の恐怖度が発生する。

最適な指示を行なったときに発生する恐怖度の合計の最小値を求めよ。

Input

入力は以下の形式で与えられる。

$N$ $M$
$U$
$A_1$ $A_2$ $...$ $A_N$
$S_1$ $T_1$ $B_1$
$S_2$ $T_2$ $B_2$
$\vdots$
$S_M$ $T_M$ $B_M$

入力はすべて整数で与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \le N \le 500$
• $0 \le M \le \min ( N \times (N-1) , 1000 )$
• $|U|=N$
• $U_i = $'L' or 'R'
• $1 \le A_i \le 1000$
• $1 \le B_i \le 1000$
• $1 \le S_i,T_i \le N$
• $(S_i,T_i) \ne (S_j,T_j), $if $ i \ne j$
• $S_i \ne T_i$

Output

恐怖度の合計の最小値を出力せよ。

Sample Input 1

3 1
RRL
5 5 1
3 1 10

Sample Output 1

1

3番目の幽霊に振り向くように指示をすると、恐怖度の合計は1となる。恐怖度の合計が0以下になるような指示は存在しないので、1を出力する。

Sample Input 2

5 5
RLRLL
9 5 1 3 10
1 3 5
2 4 9
4 2 16
1 5 2
3 5 10

Sample Output 2

8

Note

Link

 

---