問題文

とある博物館には宝石 $1, 2, ..., N$ が展示されています。 宝石 $i$ の置いてある場所は $(x_i, y_i)$ で、価値は $v_i$ です (この博物館は二次元平面として解釈できます)。

怪盗すぬけはいくつか宝石を盗みます。

宝石の盗み方には条件 $1, 2, ..., M$ があり、すべて満たさないと探偵に捕まってしまいます。 条件はそれぞれ以下の4種類のいずれかです。

• ($t_i$ =L, $a_i$, $b_i$) : 盗んだ宝石のうち、$x$ 座標が $a_i$ 以下の宝石が $b_i$ 個以下
• ($t_i$ =R, $a_i$, $b_i$) : 盗んだ宝石のうち、$x$ 座標が $a_i$ 以上の宝石が $b_i$ 個以下
• ($t_i$ =D, $a_i$, $b_i$) : 盗んだ宝石のうち、$y$ 座標が $a_i$ 以下の宝石が $b_i$ 個以下
• ($t_i$ =U, $a_i$, $b_i$) : 盗んだ宝石のうち、$y$ 座標が $a_i$ 以上の宝石が $b_i$ 個以下

怪盗すぬけが盗める宝石の価値の総和の最大値を求めてください。

制約

• $1 \\leq N \\leq 80$
• $1 \\leq x_i, y_i \\leq 100$
• $1 \\leq v_i \\leq 10^{15}$
• $1 \\leq M \\leq 320$
• $t_i$ は L, R, U, D のいずれか
• $1 \\leq a_i \\leq 100$
• $0 \\leq b_i \\leq N - 1$
• $(x_i, y_i)$ は互いに相違なる
• $(t_i, a_i)$ は互いに相違なる
• $(t_i, b_i)$ は互いに相違なる

入力

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

$N$ $x_1$ $y_1$ $v_1$ $x_2$ $y_2$ $v_2$ $:$ $x_N$ $y_N$ $v_N$ $M$ $t_1$ $a_1$ $b_1$ $t_2$ $a_2$ $b_2$ $:$ $t_M$ $a_M$ $b_M$

出力

怪盗すぬけが盗める宝石の価値の総和の最大値を出力せよ。

入力例 1

7
1 3 6
1 5 9
3 1 8
4 3 8
6 2 9
5 4 11
5 7 10
4
L 3 1
R 2 3
D 5 3
U 4 2

出力例 1

36

宝石 $1, 5, 6, 7$ を盗むと価値の総和が $36$ となります。

入力例 2

3
1 2 3
4 5 6
7 8 9
1
L 100 0

出力例 2

0

入力例 3

4
1 1 10
1 2 11
2 1 12
2 2 13
3
L 8 3
L 9 2
L 10 1

出力例 3

13

入力例 4

10
66 47 71040136000
65 77 74799603000
80 53 91192869000
24 34 24931901000
91 78 49867703000
68 71 46108236000
46 73 74799603000
56 63 93122668000
32 51 71030136000
51 26 70912345000
21
L 51 1
L 7 0
U 47 4
R 92 0
R 91 1
D 53 2
R 65 3
D 13 0
U 63 3
L 68 3
D 47 1
L 91 5
R 32 4
L 66 2
L 80 4
D 77 4
U 73 1
D 78 5
U 26 5
R 80 2
R 24 5

出力例 4

305223377000