408904: GYM103373 H A Hard Problem

H. A Hard Problemtime limit per test20.0 smemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given a simple undirected graph consisting of $$$n$$$ nodes and $$$m$$$ edges. The nodes are numbered from $$$1$$$ to $$$n$$$, and the edges are numbered from $$$1$$$ to $$$m$$$. Node $$$i$$$ has a non-negative integer value $$$V_i$$$ and the weight $$$W_{u,v}$$$ of edge $$$\{u, v\}$$$ is defined as $$$\left\|V_u\oplus V_v\right\|$$$ where $$$\oplus$$$ is the exclusive-or operator (equivalent to ^ in C) and $$$\|x\|$$$ is the number of set bits in the binary representation non-negative integer $$$x$$$

The node values $$$V_1,V_2,\dots,V_n$$$ must satisfy $$$q$$$ constraints. Each of the constraints can be represented as a 5-tuple $$$(t,u,i,v,j)$$$.

• if $$$t = 0$$$, then $$$getBit(V_u, i) = getBit(V_v, j)$$$
• if $$$t = 1$$$, then $$$getBit(V_u, i) \neq getBit(V_v, j)$$$

where the function $$$getBit(x, i)$$$ returns the $$$(i+1)$$$-th least significant bit of $$$x$$$. For examples, $$$getBit(11, 0)$$$ is $$$1$$$ and $$$getBit(11,2)=0$$$. In the C programming language, $$$getBit(x, i)$$$ can be computed by ((x » i) & 1U) if $$$x$$$ is a 32-bit unsigned integer and $$$i$$$ is a non-negative integer at most $$$31$$$.

Unfortunately, some node values are missing now. Your task is to assign new values to them to minimize $$$\sum_{\{u,v\} \in E}W_{u,v}$$$ without violating any given constraint. Please write a program to help yourself to complete this task.

Input

The input consists of five parts. The first part contains one line, and that line contains two positive integers $$$n$$$ and $$$m$$$. $$$n$$$ is the number of nodes, and $$$m$$$ is the number of edges. The second part contains $$$m$$$ lines. Each of them contains two integers $$$u$$$ and $$$v$$$, indicating an edge $$$\{u, v\}$$$ of the given graph. The third part contains one line. That line consists of $$$n$$$ space-separated integers $$$x_1,x_2,\dots,x_n$$$. For any $$$k\in\{1,2,\dots,n\}$$$, if the node value $$$V_k$$$ is missing, $$$x_k$$$ will be -1; otherwise, $$$V_k$$$ is $$$x_k$$$. The fourth part contains one integer $$$q$$$, indicating the number of constraints. The fifth part contains $$$q$$$ lines, and each of them contains five space-separated integers $$$t, u, i, v, j$$$ indicating that $$$(t, u, i, v, j)$$$ is a constraint.

• $$$1 \le n \le 1000$$$
• $$$1 \le m \le 5000$$$
• $$$-1 \le V_i < 2^{16}$$$
• $$$0 \le q \le 8$$$
• $$$t \in \{0, 1\}$$$
• $$$0 \le u, v < n$$$
• $$$0 \le i, j < 16$$$

Output

Output an integer which is the minimum value under the $$$q$$$ constraints. If it is not possible to satisfy all the constraints, output -1.

ExamplesInput

4 4
1 3
1 2
3 2
0 3
-1 -1 60091 51514 2
1 2 0 1 5
0 2 6 0 15

Output

13

Input

3 2
0 1
1 2
-1 -1 -1
2 1 2 0 1 5
0 1 5 2 0

Output

-1