#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 150;
const int INF = (-1u) >> 1;

int bit[10], p[10];
int n, a1, a2, b1, b2;
int dp[MAXN], e[2][MAXN], e2[MAXN];

inline int make_same(int u, int mask) {
    int s = mask & e[0][u], t = mask & e[1][u], ans = 0;
    for (int i = 0; i < n; i++) {
        if (!(s & bit[i]) && (t & bit[i])) ans += a1;
        else if ((s & bit[i]) && !(t & bit[i])) ans += a2;
    }
    return ans;
}

int solve() {
    int i, j;
    for (dp[0] = 0, i = 1; i < bit[n]; i++) {
        for (j = 0; j < n; j++) if (i & bit[j]) break;
        dp[i] = dp[i ^ bit[j]] + make_same(j, i ^ bit[j]);
    }
    return dp[bit[n] - 1];
}

int main() {
    int C = 0, i, j, u, v, m1, m2;
    for (i = 0; i < 10; i++) bit[i] = (1 << i);
    while (~scanf("%d%d%d", &n, &m1, &m2) && n) {
        for (i = 0; i < n; i++) e[0][i] = e2[i] = 0;
        for (i = 0; i < m1; i++) {
            scanf("%d%d", &u, &v);
            e[0][u] |= bit[v];
            e[0][v] |= bit[u];
        }
        for (i = 0; i < m2; i++) {
            scanf("%d%d", &u, &v);
            e2[u] |= bit[v];
            e2[v] |= bit[u];
        }
        scanf("%d%d%d%d", &a1, &a2, &b1, &b2);
        a1 = min(a1, b2), a2 = min(a2, b1);
        for (i = 0; i < n; i++) p[i] = i;
        int ans = INF;
        do {
            for (i = 0; i < n; i++) {
                e[1][i] = 0, u = p[i];
                for (j = 0; j < n; j++) {
                    if (e2[u] & bit[p[j]]) e[1][i] |= bit[j];
                }
            }
            if (p[0] == 0 && p[1] == 1 && p[3] == 2) {for (i = 0; i < n; i++) printf("%d ", e[1][i]); puts("");}
            ans = min(ans, solve());
        } while (next_permutation(p, p + n));
        printf("Case #%d: %d\n", ++C, ans);
    }
    return 0;
}