AT_agc031_e [AGC031E] Snuke the Phantom Thief

某博物馆展出了宝石 $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 \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 翻译