Red-Black Boolean Expression SOLUTION RB2CNF

Red-Black Boolean Expression November Challenge 2020

Let S be a set of N boolean variables X1,X2,…,XN and their negations ¬X1,¬X2,…,¬XN. You are given the initial values of all variables.

A 2-CNF boolean expression is defined as a conjunction of clauses, where each clause is a disjunction of two elements of the set S. Ada constructed a 2-CNF boolean expression B with M clauses as follows:

First, Ada painted each of the variables X1,X2,…,XN with one colour ― either red or black.

Then, she painted the negated variables ― for each valid i, if Xi is painted red, then ¬Xi is painted black, and vice versa (if Xi is black, ¬Xi is painted red).

Finally, she wrote the boolean expression B=(P1∨Q1)∧(P2∨Q2)∧…∧(PM∨QM), in such a way that no clause contains two variables with the same colour and Pi≠¬Qi for each clause.

Ada wants the expression to evaluate to “true”. In order to achieve that, she may change the values of variables; for each valid i, changing the value of Xi (from “true” to “false” or vice versa) is Ci. Find the minimum total cost needed to make the expression B evaluate to “true” or determine that it is impossible.

Note that you are not given the colours of variables, but it is guaranteed that the expression B is chosen in such a way that there is at least one valid way to assign colours and the minimum cost is the same for each valid assignment of colours.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space-separated integers N and M.

The second line contains a binary string S with length N describing the initial values of the variables. For each valid i, the i-th character of S is ‘1’ if Xi is true or ‘0’ if Xi is false.

The third line contains N space-separated integers C1,C2,…,CN.

M lines follow. For each valid i, the i-th of these lines contains two space-separated integers Pi and Qi. For each valid i, the variable Xi is represented by the integer i and its negation is represented by −i.

Output

For each test case, print a single line containing one integer ― the minimum cost needed to make the boolean expression evaluate to “true”, or −1 if it is impossible.

Constraints

1≤T≤105

1≤N≤256

1≤Ci≤256 for each valid i

1≤|Pi|,|Qi|≤N for each valid i

each character of S is either ‘0’ or ‘1’

the sum of M over all test cases does not exceed 43,210

Subtasks

Subtask #1 (1 points): N≤10

Subtask #2 (99 points): original constraints

Example Input

1

3 3

101

1 2 3

-1 -2

-1 -3

2 1

Example Output

3

Explanation

Example case 1: The expression B is (¬X1∨¬X2)∧(¬X1∨¬X3)∧(X2∨X1). Ada generated this expression by painting X2 and X3 in red and X1 in black.

One optimal way to make the expression true is changing the value of X3.

CLICK HERE