Welcome to ZOJ
 Problem Sets 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.

```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