题目描述

某博物馆展出了宝石 $1, 2, \ldots, N$。宝石 $i$ 的位置为 $(x_i, y_i)$，价值为 $v_i$（可以将博物馆看作一个二维平面）。

怪盗すぬけ计划偷取若干宝石。

偷取宝石的方式需要满足 $1, 2, \ldots, M$ 条条件，若有任一条件不满足，则会被侦探抓住。每条条件属于以下四种之一：

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

请你求出怪盗すぬけ能够偷取的宝石的最大总价值。

输入格式

输入按以下格式从标准输入读入。

$N$ $x_1$ $y_1$ $v_1$ $x_2$ $y_2$ $v_2$ $\ldots$ $x_N$ $y_N$ $v_N$ $M$ $t_1$ $a_1$ $b_1$ $t_2$ $a_2$ $b_2$ $\ldots$ $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

输出

36

样例 2

输入

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

输出

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

输出

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

输出

305223377000

说明/提示

限制条件

• $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)$ 互不相同

样例解释 1

如果偷取宝石 $1, 5, 6, 7$，则总价值为 $36$。

由 ChatGPT 4.1 翻译