問題文
とある博物館には宝石 1,2,...,N が展示されています。 宝石 i の置いてある場所は (xi,yi) で、価値は vi です (この博物館は二次元平面として解釈できます)。
怪盗すぬけはいくつか宝石を盗みます。
宝石の盗み方には条件 1,2,...,M があり、すべて満たさないと探偵に捕まってしまいます。 条件はそれぞれ以下の4種類のいずれかです。
- (ti =
L
, ai, bi) : 盗んだ宝石のうち、x 座標が ai 以下の宝石が bi 個以下
- (ti =
R
, ai, bi) : 盗んだ宝石のうち、x 座標が ai 以上の宝石が bi 個以下
- (ti =
D
, ai, bi) : 盗んだ宝石のうち、y 座標が ai 以下の宝石が bi 個以下
- (ti =
U
, ai, bi) : 盗んだ宝石のうち、y 座標が ai 以上の宝石が bi 個以下
怪盗すぬけが盗める宝石の価値の総和の最大値を求めてください。
制約
- 1leqNleq80
- 1leqxi,yileq100
- 1leqvileq1015
- 1leqMleq320
- ti は
L
, R
, U
, D
のいずれか
- 1leqaileq100
- 0leqbileqN−1
- (xi,yi) は互いに相違なる
- (ti,ai) は互いに相違なる
- (ti,bi) は互いに相違なる
入力
入力は以下の形式で標準入力から与えられる。
N
x1 y1 v1
x2 y2 v2
:
xN yN vN
M
t1 a1 b1
t2 a2 b2
:
tM aM bM
出力
怪盗すぬけが盗める宝石の価値の総和の最大値を出力せよ。
入力例 1
出力例 1

宝石 1,5,6,7 を盗むと価値の総和が 36 となります。
入力例 2
出力例 2
入力例 3
出力例 3
入力例 4
出力例 4