Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3579
Gao the variable

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Given n boolean variables and the result of m operations, calculate the maximum score you can get. The value of each variable only can be 0 or 1. The score is calculated by p rules. Each rule will be defined by five integers (i,x,j,y,w). It means that you can get w scores if the value of the i-th variable equal to x and the value of the j-th variable equal to y. Now, determine the value of each variable so that you can get the maximum score.

Input

There are multiple test cases. The first line of each case contains three integer n m p( 1 ≤ n,m ≤ 100 , 1 ≤ p ≤ 5000 ).

Then following m lines, each describe a result of an operation. The format of each line is : i [operation] j = x ( 1 ≤ i,j ≤ n , 0 ≤ x ≤ 1 ). It gives the result of the i-th variable and the j-th variable on the operation.

There are only three kinds of operation("and","xor","or") in the data. The next p lines give the rules using format : i x j y w( 1 ≤ i,j ≤ n , 0 ≤ x,y ≤ 1 , 0 ≤ w ≤ 50 ). Process to the end of file.

Output

Output one line for each case. That is the maximum score you can get. I guarantee that there is at least one solution can satisfy the m operations.

Sample Input

3 2 2
1 xor 2 = 1
1 and 3 = 0
1 1 2 0 1
3 1 3 1 10

Sample Output

10

Author: CHEN, Weijie
Contest: ZOJ Monthly, February 2012
Submit    Status