问题描述

一个博物馆展示了$N$颗宝石，宝石分别记为$1, 2, ..., N$。第$i$颗宝石的坐标是$(x_i, y_i)$（博物馆可以看作一个二维平面），宝石的价值是$v_i$。

小偷Snuke将偷走其中一些宝石。

有$M$个条件，条件$1, 2, ..., M$，在偷取宝石时必须满足，否则他会被侦探抓住。每个条件有以下四种形式之一：

• ($t_i$ =L, $a_i$, $b_i$) ：Snuke只能最多偷取$x$坐标小于等于$a_i$的$b_i$颗宝石。
• ($t_i$ =R, $a_i$, $b_i$) ：Snuke只能最多偷取$x$坐标大于等于$a_i$的$b_i$颗宝石。
• ($t_i$ =D, $a_i$, $b_i$) ：Snuke只能最多偷取$y$坐标小于等于$a_i$的$b_i$颗宝石。
• ($t_i$ =U, $a_i$, $b_i$) ：Snuke只能最多偷取$y$坐标大于等于$a_i$的$b_i$颗宝石。

找出Snuke小偷能够偷取的宝石的价值的最大总和。

约束条件

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

输出

输出Snuke小偷能够偷取的宝石的价值的最大总和。

示例输入 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