#include #include #include #include using namespace std; typedef long long ll; template struct edge { int a, b; int preference_a, preference_b; bool is_matched; T cost; int id; bool operator<(const edge &e) const { return preference_a < e.preference_a; } }; template struct stable_matching { static const int MALE = 0; static const int FEMALE = 1; int p, q, m; std::vector>> g; std::vector> epos; stable_matching() {} stable_matching(int p, int q) : p(p), q(q), m(0) { g.resize(p); } void add_directed_edge(int a, int b, int preference_a, int preference_b, int cost = 1) { assert(0 <= a && a < p); assert(0 <= b && b < q); epos.push_back(std::pair(a, (int)g[a].size())); g[a].push_back((edge){a, b, preference_a, preference_b, false, cost, m++}); } void get_stable_matching() { for (int a = 0; a < p; a++) { if (!std::is_sorted(g[a].begin(), g[a].end())) { std::sort(g[a].begin(), g[a].end()); } } std::vector> mbpos(q, std::pair(-1, -1)); std::vector nx(p, 0); std::queue que; for (int a = 0; a < p; a++) { que.push(a); } while (que.size()) { int a = que.front(); que.pop(); for (int &i = nx[a]; i < (int)g[a].size(); i++) { int b = g[a][i].b; int x = mbpos[b].first; if (x >= 0 && g[x][mbpos[b].second].preference_b > g[a][i].preference_b) { g[x][mbpos[b].second].is_matched = false; nx[x]++; que.push(x); x = -1; } if (x == -1) { g[a][i].is_matched = true; mbpos[b] = std::pair(a, i); break; } } } } edge &get_edge(int id) { assert(id < m); return g[epos[id].first][epos[id].second]; } }; void solve() { int n, x, y; cin >> n >> x >> y; int p[200005], d[200005]; for (int u = 0; u < n; u++) { p[u] = -1; } int k[200005]; for (int i = 0; i < x; i++) { cin >> k[i]; for (int j = 0; j <= k[i]; j++) { int u; cin >> u; u--; p[u] = i; d[u] = j; } } stable_matching g(x, y); int m = 0; for (int i = 0; i < y; i++) { int k; cin >> k; for (int j = 0; j <= k; j++) { int u; cin >> u; u--; if (p[u] >= 0) { g.add_directed_edge(i, p[u], -j, d[u]); } } } g.get_stable_matching(); int ans = 0; for (int i = 0; i < x; i++) { ans += k[i]; } for (int i = 0; i < g.m; i++) { edge e = g.get_edge(i); if (e.is_matched) { ans -= k[e.b] - e.preference_b; } } cout << ans << endl; } int main() { solve(); }