Problem: The Hexadecimal virus loves playing with number sets — intersecting them, uniting them. One beautiful day she was surprised to find out that Scuzzy, her spherical pet cat, united all sets in one and ate the result! Something had to be done quickly and Hexadecimal rushed to the market.

The market has n sets of numbers on sale. The virus wants to buy the following collection of sets: the number of sets in the collection should be exactly the same as the number of numbers in the union of all bought sets. Moreover, Hexadecimal wants to buy the cheapest suitable collection of set.

Yet nothing's so easy! As Mainframe is a kingdom of pure rivalry markets, we know that the union of any k sets contains no less than k distinct numbers (for every positive integer k).

Help the virus choose the suitable collection of sets. The collection can be empty.

Input

The first line contains the only number n (1 ≤ n ≤ 300) — the number of sets available in the market.

Next n lines describe the goods: first we are given mi (1 ≤ mi ≤ n) — the number of distinct numbers in the i-th set, then follow mi numbers — the set's elements. We know that the set's elements are distinct positive integers and they do not exceed n.

The last line contains n integers whose absolute values do not exceed 106 — the price of each set.

Output

Print a single number — the minimum price the virus will have to pay for such a collection of k sets that union of the collection's sets would have exactly k distinct numbers (<image>).

Examples

Input

3
1 1
2 2 3
1 3
10 20 -3


Output

-3


Input

5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
1 -1 1 -1 1


Output

0


Input

5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
-1 1 -1 1 -1


Output

-1

Solution (in JAVA):

Solution:
import java.util.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.util.Collection;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    private static final int INF = Integer.MAX_VALUE / 2;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        boolean[][] g = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            int count = in.nextInt();
            for (int j = 0; j < count; ++j) {
                int x = in.nextInt() - 1;
                g[i][x] = true;
            }
        }
        int[] res = new int[n];
        Arrays.fill(res, -1);
        boolean[] u = new boolean[n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(u, false);
            dfs(i, g, u, res);
        }
        Graph g2 = new Graph();
        int[] cost = Utils.readIntArray(in, n);
        g2.initGraphWithFlow(n + 2, n * n + 2, n, n + 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!g[i][j]) continue;
                if (res[j] == i) continue;
                int jj = res[j];
                g2.addFlowEdge(i, jj, INF);
            }
        }
        int S = n;
        int T = n + 1;
        long result = 0;
        for (int i = 0; i < n; ++i) {
            if (cost[i] > 0) {
                g2.addFlowEdge(i, T, cost[i]);
            } else if (cost[i] < 0) {
                result -= cost[i];
                g2.addFlowEdge(S, i, -cost[i]);
            }
        }
        long value = MaxFlowDinic.dinic(g2, S, T);
        out.println(value - result);
    }

    private boolean dfs(int v, boolean[][] g, boolean[] u, int[] res) {
        if (u[v]) return false;
        u[v] = true;
        for (int i = 0; i < g[v].length; ++i) {
            if (g[v][i]) {
                if (res[i] == -1 || dfs(res[i], g, u, res)) {
                    res[i] = v;
                    return true;
                }
            }
        }
        return false;
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class Graph {
    public int[] from;
    public int[] to;
    public int[] first;
    public int[] next;
    public int[] cost;
    public int[] capacity;
    public long[] flow;
    public int[] last;
    public int nVertex;
    public int nEdges;
    int[] reverseEdge;
    public int curEdge;
    int source;
    int dest;

    public Graph() {}

    public void initGraphWithFlow(int n, int m, int source, int dest) {
        curEdge = 0;
        nVertex = n;
        nEdges = m;
        from = new int[m * 2];
        to = new int[m * 2];
        first = new int[n];
        next = new int[m * 2];
        cost = new int[m * 2];
        capacity = new int[m * 2];
        flow = new long[m * 2];
        reverseEdge = new int[m * 2];
        last = new int[m * 2];
        this.source = source;
        this.dest = dest;
        Arrays.fill(first, -1);
        Arrays.fill(last, -1);
    }

    public void addFlowEdge(int a, int b, int f) {
//        System.err.println("Added edge " + a + " - " + b + " with flow: " + f);
        next[curEdge] = first[a];
        first[a] = curEdge;
        to[curEdge] = b;
        from[curEdge] = a;
        capacity[curEdge] = f;
        flow[curEdge] = 0;
        reverseEdge[curEdge] = curEdge + 1;
        ++curEdge;

        next[curEdge] = first[b];
        first[b] = curEdge;
        to[curEdge] = a;
        from[curEdge] = b;
        capacity[curEdge] = 0;
        flow[curEdge] = 0;
        reverseEdge[curEdge] = curEdge - 1;
        ++curEdge;
    }

    public final void pushFlow(int id, long fl) {
        if (fl == 0) {
            return;
        }
        if (fl > 0) {
            if (capacity[id] < fl) {
                throw new IllegalArgumentException("Not enough capacity");
            }
        } else {
            if (flow[id] < -fl) {
                throw new IllegalArgumentException("Not enough capacity");
            }
        }
        capacity[id] -= fl;
        capacity[id ^ 1] += fl;
    }
}

class Utils {
    public static int[] readIntArray(InputReader in, int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        return a;
    }

}

class MaxFlowDinic {
    private final Graph graph;
    private int source;
    private int dest;
    private int[] queue;
    private int[] distance;
    private int[] nextEdge;

    public MaxFlowDinic(Graph graph, int source, int dest) {
        this.graph = graph;
        this.source = source;
        this.dest = dest;
        int n = graph.nVertex;
        queue = new int[n];
        distance = new int[n];
        nextEdge = new int[n];
    }

    public static long dinic(Graph graph, int source, int destination) {
        return new MaxFlowDinic(graph, source, destination).dinic();
    }

    private long dinic() {
        long totalFlow = 0;
        while (true) {
            edgeDistances();
            if (distance[dest] == -1)
                break;
            Arrays.fill(nextEdge, -2);
            totalFlow += dinicImpl(source, Long.MAX_VALUE);
        }
        return totalFlow;
    }

    private void edgeDistances() {
        Arrays.fill(distance, -1);
        distance[source] = 0;
        int size = 1;
        queue[0] = source;
        for (int i = 0; i < size; i++) {
            int cur = queue[i];
            for (int id = graph.first[cur]; id != -1; id = graph.next[id]) {
                if (graph.capacity[id] != 0) {
                    int next = graph.to[id];
                    if (distance[next] == -1) {
                        distance[next] = distance[cur] + 1;
                        queue[size++] = next;
                    }
                }
            }
        }
    }

    private long dinicImpl(int source, long flow) {
        if (source == dest)
            return flow;
        if (flow == 0 || distance[source] == distance[dest])
            return 0;
        int id = nextEdge[source];
        if (id == -2)
            nextEdge[source] = id = graph.first[source];
        long totalPushed = 0;
        while (id != -1) {
            int nextDestinationID = graph.to[id];
            if (graph.capacity[id] != 0 && distance[nextDestinationID] == distance[source] + 1) {
                long pushed = dinicImpl(nextDestinationID, Math.min(flow, graph.capacity[id]));
                if (pushed != 0) {
                    graph.pushFlow(id, pushed);
                    flow -= pushed;
                    totalPushed += pushed;
                    if (flow == 0)
                        return totalPushed;
                }
            }
            nextEdge[source] = id = graph.next[id];
        }
        return totalPushed;
    }
}