← 返回题目列表

AtCoder · agc031_e

E. 潜伏怪盗

中文机器翻译题面 查看原题

分数: 1300 点

问题陈述

博物馆展品 N 珠宝,珠宝 1, 2, ..., N。 宝石的坐标 i 是 (x_i, y_i) (博物馆可以看成是一个二维平面),那颗宝石的价值是 v_i.

潜伏小偷会偷走其中一些珠宝。

有 M 条件,条件 1, 2, ..., M,偷珠宝时必须满足这个条件,否则就会被侦探抓住。 每个条件都有以下四种形式之一:

  • (t_i =L, a_i, b_i) : Snuke 最多只能偷窃 b_i 珠宝 x 坐标是 a_i 或更小。
  • (t_i =R, a_i, b_i) : Snuke 最多只能偷窃 b_i 珠宝 x 坐标是 a_i 或更大。
  • (t_i =D, a_i, b_i) : Snuke 最多只能偷窃 b_i 珠宝 y 坐标是 a_i 或更小。
  • (t_i =U, a_i, b_i) : Snuke 最多只能偷窃 b_i 珠宝 y 坐标是 a_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 is L, R, U or 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

Figure

偷宝石 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