Problem Statement

A museum exhibits $N$ jewels, Jewel $1, 2, ..., N$. The coordinates of Jewel $i$ are $(x_i, y_i)$ (the museum can be regarded as a two-dimensional plane), and the value of that jewel is $v_i$.

Snuke the thief will steal some of these jewels.

There are $M$ conditions, Condition $1, 2, ..., M$, that must be met when stealing jewels, or he will be caught by the detective. Each condition has one of the following four forms:

• ($t_i$ =L, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $x$ coordinates are $a_i$ or smaller.
• ($t_i$ =R, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $x$ coordinates are $a_i$ or larger.
• ($t_i$ =D, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $y$ coordinates are $a_i$ or smaller.
• ($t_i$ =U, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $y$ coordinates are $a_i$ or larger.

Find the maximum sum of values of jewels that Snuke the thief can steal.

Constraints

• $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)$ are pairwise distinct.
• $(t_i, a_i)$ are pairwise distinct.
• $(t_i, b_i)$ are pairwise distinct.

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum sum of values of jewels that Snuke the thief can steal.