分数: 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,UorD. - 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