For given integers N let’s consider the following single player game played with a box, N black and N white balls. Initially the box is empty and in one move the player can:
throw any ball not currently in the box into it
take out any ball currently in the box
if the box is empty, in one move he can put all $2 \cdot N$ balls inside
if the box contains $2 \cdot N$ balls, he can take away all of them in one move

Moreover, there are additional $2 \cdot Q_v$ different valid moves given by Q_v rules and each single rule is given by 4 integers:

$b, w, \delta_b, \delta_w$

and means that if there are exactly b black balls and exactly w white balls in the box, then in one move the player can add/remove balls in such a way that after the move there are $b + \delta_b$ black and $w + \delta_w$ white balls in the box. In addition, the reverse operation is also a valid move, which means that if there are exactly $b + \delta_b$ black and exactly $w + \delta_w$ white balls in the box, the player can in one move add/remove balls in such a way that after the move there are exactly b black and exactly w white balls in the box.

Moreover, there are $2 \cdot Q_f$ different forbidden moves given by Q_f rules and each such rule is given by 3 values:

$b_f, w_f, c$

where 0 ≤q b_f, w_f < N and denotes that if there are exactly b_f black and exactly w_f white balls in the box, the player cannot add to the box a ball of color c. In addition, the reverse operation is also a forbidden move, which means that for example if c is WHITE then the player cannot add a white ball to the box if there are exactly b_f black and exactly w_f white balls already there, and moreover, he cannot remove a white ball from the box if there are exactly b_f black and exactly w_f white balls already there.

Now let’s consider any valid state of the box during the game with exactly b black and w white balls inside. The evaluation of then box is then defined as $b \cdot w$.

Next let’s consider a monkey playing the game forever. Monkey knows all the rules and makes only allowed moves. However, she doesn’t know what’s the best move in any situation, so she choses any of possible moves uniformly at random and performs it.

The goal of this problem is to find the greatest sum of evaluations of two boxes X, Y that can be produced during the game played by monkey, such that monkey can move from X to Y in a single move and she can move from Y to X in a single move also, and the expected number of moves the monkey will make in order to transform the box X to box Y and then back to X is an integer divisible by the number of all possible different moves monkey can make during the game. Two moves are the same if and only if they transform the same current state to the same state using the same operation including the same number of balls of every color.

If there are no two such boxes, then the answer is -1.

Constraints:
1 ≤q N ≤q 300
0 ≤q Q_v ≤q 100
0 ≤q Q_f ≤q 1000
$0 < |\delta_b|, |\delta_w| < N$
0 ≤$q b + \delta_b, w + \delta_w$ ≤q N
for any 0 ≤q w, b ≤q N the box containing b black and w white balls can be produces by a sequence of valid moves
c is either BLACK or WHITE
0 ≤q b_f, w_f < N
all additional moves are unique and all of them are different than standard valid moves given at the beginning of the statement
all forbidden moves are unique
for a forbidden move the number of black balls in the box before and after the move cannot be both N
for a forbidden move the number of white balls in the box before and after the move cannot be both 0

Subtask 1 (10 pts):
N ≤q 10

Subtask 2 (30 pts):
N ≤q 50

Subtask 3 (60 pts):
N ≤q 300

Input format:

In the first line there are three space separated integers N, Q_v, Q_f denoting the number of balls of each colors, the number of rules describing additional valid moves and the number of rules describing forbidden moves. Then Q_v lines follow and in each of them there are $4 space separated integers b, w, \delta_b, \delta_w denoting a$ rule describing two additional valid moves. After that Q_f lines follow and in each of them there are 3 space separated values b_f, w_f, c denoting a rule describing two forbidden moves.

Output format:

In a single line output one integer denoting the greatest sum of evaluations of two boxes X, Y during the game played by monkey, such that monkey can move from X to Y in a single move and she can move from Y to X in a single move also, and the expected number of moves the monkey will make in order to transform the box X to box Y and then back to X is an integer divisible by the number of all possible different moves monkey can make during the game. If there are any such boxes, print -1 in a single line.

SAMPLE INPUT
1 0 1
0 0 WHITE

SAMPLE OUTPUT
1

Explanation

There are only 1 black and 1 white ball in the game and a total of 8 different possible valid moves. The only pair of boxes X, Y for which the wanted constraints is fulfilled is:
box X contains exactly 1 white ball and no black balls
box Y contains exactly 1 black and exactly 1 white ball

The answer is 1, because the evaluation of box X is $1 \cdot 0 = 0$, the evaluation of box Y is $1 \cdot 1 = 1$, and the sum of these evaluations is 1.

见题面

见题面