We say that two graphs are equivalent if and only if a one-to-one correspondence between their nodes can be established and under such a correspondence their edges are exactly the same. Given A and B, two undirected simple graphs with the same number of vertexes, you are to find a series of operations with the minimum cost that will make the two graphs equivalent. An operation may be one of the following two types:
a) Add an arbitrary edge (x, y), provided that (x, y) does not exist before such an operation. Such an operation costs I
A and I
B on two graphs, respectively.
b) Delete an existing edge (x, y), which costs D
A and D
B on two graphs,respectively.
There are multiple test cases in the input file.
Each test case starts with three integers, N, M
A and M
B, ( 1 ≤ N ≤ 8, 0 ≤ M
B ,M
A ≤ N*(N-1)/2 ), the total number of vertexes, the number of edges in graph A,and the number of edges in graph B, respectively. Four integers I
A, I
B, D
A, and D
B come next, (0 ≤ I
A, I
B, D
A, D
B ≤ 32767 ), representing the costs as stated in the problem description. The next M
A + M
B lines describe the edges in graph A followed by those in graph B. Each line consists of exactly two integers, X and Y ( X ≠ Y , 0 ≤ X,Y < N).
Two successive test cases are separated by a blank line. A case with N = 0, M
A = 0,and M
B = 0 indicates the end of the input file, and should not be processed by your program.
Please print the minimum cost in the format as illustrated below.