← Home
```go
package main

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

const INF int64 = 1e16

type Edge struct {
	to  int
	cap int64
	rev int
}

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

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

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

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

func dfsDinic(v, t int, pushed int64) int64 {
	if pushed == 0 || v == t {
		return pushed
	}
	for ptr[v] < len(graph[v]) {
		idx := ptr[v]
		edge := graph[v][idx]
		tr := edge.to
		if level[v]+1 != level[tr] || edge.cap == 0 {
			ptr[v]++
			continue
		}
		push := dfsDinic(tr, t, min(pushed, edge.cap))
		if push == 0 {
			ptr[v]++
			continue
		}
		graph[v][idx].cap -= push
		graph[tr][edge.rev].cap += push
		return push
	}
	return 0
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	nextInt := func() int {
		scanner.Scan()
		res, _ := strconv.Atoi(scanner.Text())
		return res
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())

	sets := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		m := nextInt()
		sets[i] = make([]int, m)
		for j := 0; j < m; j++ {
			sets[i][j] = nextInt()
		}
	}

	costs := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		costs[i] = int64(nextInt())
	}

	match := make([]int, n+1)
	for i := range match {
		match[i] = -1
	}

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

	S := 0
	T := n + 1
	graph = make([][]Edge, T+1)
	level = make([]int, T+1)
	ptr = make([]int, T+1)

	var sumWPos int64 = 0

	for i := 1; i <= n; i++ {
		w := -costs[i]
		if w > 0 {
			addEdge(S, i, w)
			sumWPos += w
		} else if w < 0 {
			addEdge(i, T, -w)
		}

		for _, x := range sets[i] {
			j := match[x]
			if j != -1 && i != j {
				addEdge(i, j, INF)
			}
		}
	}

	var flow int64 = 0
	for bfs(S, T) {
		for i := range ptr {
			ptr[i] = 0
		}
		for {
			pushed := dfsDinic(S, T, INF)
			if pushed == 0 {
				break
			}
			flow += pushed
		}
	}

	ans := flow - sumWPos
	fmt.Println(ans)
}
```