SOLVE
LATER
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:
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 \leq 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:
Subtask 1 (10 pts):
Subtask 2 (30 pts):
Subtask 3 (60 pts):
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.
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:
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.