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 IA and IB on two graphs, respectively. b) Delete an existing edge (x, y), which costs DA and DB on two graphs,respectively.

There are multiple test cases in the input file. Each test case starts with three integers, N, MA and MB, ( 1 ≤ N ≤ 8, 0 ≤ MB ,MA ≤ 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 IA, IB, DA, and DB come next, (0 ≤ IA, IB, DA, DB ≤ 32767 ), representing the costs as stated in the problem description. The next MA + MB 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, MA = 0,and MB = 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.

2008 Asia Regional Hangzhou