← Home
package main

import (
	"bufio"
	"fmt"
	"os"
)

const INF int64 = 1000000000000000000

type Edge struct {
	to, rev   int
	cap, flow int64
}

var (
	graph [][]Edge
	level []int
	ptr   []int
)

func addEdge(u, v int, cap int64) {
	graph[u] = append(graph[u], Edge{v, len(graph[v]), cap, 0})
	graph[v] = append(graph[v], Edge{u, len(graph[u]) - 1, 0, 0})
}

func bfs(s, t int) bool {
	for i := range level {
		level[i] = -1
	}
	level[s] = 0
	queue := []int{s}
	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		for _, e := range graph[u] {
			if e.cap-e.flow > 0 && level[e.to] == -1 {
				level[e.to] = level[u] + 1
				queue = append(queue, e.to)
			}
		}
	}
	return level[t] != -1
}

func dfs(u, t int, pushed int64) int64 {
	if pushed == 0 {
		return 0
	}
	if u == t {
		return pushed
	}
	for ptr[u] < len(graph[u]) {
		e := &graph[u][ptr[u]]
		tr := e.to
		if level[u]+1 != level[tr] || e.cap-e.flow == 0 {
			ptr[u]++
			continue
		}
		push := pushed
		if e.cap-e.flow < push {
			push = e.cap - e.flow
		}
		pushedFlow := dfs(tr, t, push)
		if pushedFlow == 0 {
			ptr[u]++
			continue
		}
		e.flow += pushedFlow
		graph[tr][e.rev].flow -= pushedFlow
		return pushedFlow
	}
	return 0
}

func dinic(s, t int) int64 {
	var flow int64 = 0
	for bfs(s, t) {
		for i := range ptr {
			ptr[i] = 0
		}
		for {
			pushed := dfs(s, t, INF)
			if pushed == 0 {
				break
			}
			flow += pushed
		}
	}
	return flow
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n int
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}

	adj := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		var m int
		fmt.Fscan(in, &m)
		adj[i] = make([]int, m)
		for j := 0; j < m; j++ {
			fmt.Fscan(in, &adj[i][j])
		}
	}

	cost := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &cost[i])
	}

	match := make([]int, n+1)
	for i := 1; i <= n; i++ {
		visited := make([]bool, n+1)
		var dfsMatch func(int) bool
		dfsMatch = func(u int) bool {
			for _, v := range adj[u] {
				if !visited[v] {
					visited[v] = true
					if match[v] == 0 || dfsMatch(match[v]) {
						match[v] = u
						return true
					}
				}
			}
			return false
		}
		dfsMatch(i)
	}

	graph = make([][]Edge, n+2)
	level = make([]int, n+2)
	ptr = make([]int, n+2)
	src := 0
	snk := n + 1

	var sumNeg int64 = 0
	for i := 1; i <= n; i++ {
		if cost[i] < 0 {
			addEdge(src, i, -cost[i])
			sumNeg += cost[i]
		} else if cost[i] > 0 {
			addEdge(i, snk, cost[i])
		}
		for _, v := range adj[i] {
			j := match[v]
			if i != j && j != 0 {
				addEdge(i, j, INF)
			}
		}
	}

	ans := sumNeg + dinic(src, snk)
	fmt.Println(ans)
}