[AGC031E] Snuke the Phantom Thief

在二维平面上，有 $n$ 颗珠宝，第$i$颗珠宝在 $(x_i,y_i)$ 的位置，价值为 $v_i$。 现在有一个盗贼想要偷这些珠宝。 现在给出 $m$ 个限制约束偷的珠宝，约束有以下四种： + 横坐标小于等于 $a_i$ 的珠宝最多偷 $b_i$ 颗。 + 横坐标大于等于 $a_i$ 的珠宝最多偷 $b_i$ 颗。 + 纵坐标小于等于 $a_i$ 的珠宝最多偷 $b_i$ 颗。 + 纵坐标大于等于 $a_i$ 的珠宝最多偷 $b_i$ 颗。 这四个限制输入的时候分别用LRDU四个字母来区分。 现在问你在满足这些约束的条件下，盗贼偷的珠宝的最大价值和是多少。

[problemUrl]: https://atcoder.jp/contests/agc031/tasks/agc031_e とある博物館には宝石 $ 1,\ 2,\ ...,\ N $ が展示されています。 宝石 $ i $ の置いてある場所は $ (x_i,\ y_i) $ で、価値は $ v_i $ です (この博物館は二次元平面として解釈できます)。 怪盗すぬけはいくつか宝石を盗みます。 宝石の盗み方には条件 $ 1,\ 2,\ ...,\ M $ があり、すべて満たさないと探偵に捕まってしまいます。 条件はそれぞれ以下の4種類のいずれかです。 - ($ 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 $ $ : $ $ 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 $

怪盗すぬけが盗める宝石の価値の総和の最大値を出力せよ。

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

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

0

4
1 1 10
1 2 11
2 1 12
2 2 13
3
L 8 3
L 9 2
L 10 1

13

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) $ は互いに相違なる ### Sample Explanation 1 !\[図\](https://img.atcoder.jp/agc031/rghe0iwfjoievjw4epdfmengow.png) 宝石 $ 1,\ 5,\ 6,\ 7 $ を盗むと価値の総和が $ 36 $ となります。