この問題は、最大流問題を用いて解くことができます。

\(S,T\) および参加者 \(i\ (1\le i\le N)\) 、\(j\) 番目の種類のプレゼント \((1\le j\le M)\) からなる \(2+N+M\) 個の頂点をもつグラフを考え、次のような辺を張ります。

• \(S\) から参加者 \(i\) へ向かう容量 \(1\) の辺 \((1\le i\le N)\)
• 参加者 \(i\) から \(C _ {i,j}\) 番目の種類のプレゼントへ向かう容量 \(1\) の辺 \((1\le i\le N,1\le j\le K _ i)\)
• \(j\) 番目の種類のプレゼントから \(T\) へ向かう容量 \(B _ j\) の辺 \((1\le j\le M)\)

このグラフにおける \(S\) から \(T\) への最大流が求める答えになります。

Dinic 法を使うと、辺容量が整数であることと最大流がたかだか \(N\) であることから時間計算量は \(O(N ^ 2M)\) となり、十分高速です。

実装例は以下のようになります。

#include <iostream>
#include <atcoder/maxflow>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    atcoder::mf_graph<int> G(1 + N + M + 1);
    // S から参加者への辺
    for (int i = 0; i < N; ++i) {
        G.add_edge(0, 1 + i, 1);
    }
    // プレゼントから T への辺
    for (int i = 0; i < M; ++i) {
        int B;
        cin >> B;
        G.add_edge(1 + N + i, 1 + N + M + 0, B);
    }
    // 参加者からプレゼントへの辺
    for (int i = 0; i < N; ++i) {
        int K;
        cin >> K;
        for (int j = 0; j < K; ++j) {
            int C;
            cin >> C;
            --C;
            G.add_edge(1 + i, 1 + N + C, 1);
        }
    }

    // S から T への最大流が答え
    cout << G.flow(0, 1 + N + M + 0) << endl;
    return 0;
}

from atcoder.maxflow import MFGraph


N, M = map(int, input().split())

G = MFGraph(1 + N + M + 1)
# S から参加者への辺
for i in range(N):
    G.add_edge(0, 1 + i, 1)
# プレゼントから T への辺
for i, B in enumerate(map(int, input().split())):
    G.add_edge(1 + N + i, 1 + N + M + 0, B)
# 参加者からプレゼントへの辺
for i in range(N):
    K, *C = map(int, input().split())
    for c in C:
        G.add_edge(1 + i, 1 + N + c - 1, 1)

# S から T への最大流が答え
print(G.flow(0, 1 + N + M + 0))