// code template is in https://github.com/drken1215/algorithm/blob/master/template_minimum.cpp #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; //------------------------------// // Utility //------------------------------// using ll = long long; using i128 = __int128_t; using u128 = __uint128_t; using pint = pair; using pll = pair; using tll = array; using fll = array; using vint = vector; using vll = vector; using dint = deque; using dll = deque; using vvint = vector>; using vvll = vector>; using vpll = vector>; template using min_priority_queue = priority_queue, greater>; template inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); } template inline auto maxll(S a, T b) { return max(ll(a), ll(b)); } template inline auto minll(S a, T b) { return min(ll(a), ll(b)); } template auto max(const T &a) { return *max_element(a.begin(), a.end()); } template auto min(const T &a) { return *min_element(a.begin(), a.end()); } template auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); } template auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); } template auto accum(const vector &a) { return accumulate(a.begin(), a.end(), T()); } template auto accum(const deque &a) { return accumulate(a.begin(), a.end(), T()); } #define REP(i, a) for (long long i = 0; i < (long long)(a); i++) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++) #define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i) #define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i) #define EB emplace_back #define PF push_front #define PB push_back #define MP make_pair #define FI first #define SE second #define ALL(x) x.begin(), x.end() #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl // input template istream& operator >> (istream &is, vector &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } template istream& operator >> (istream &is, deque &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } template istream& operator >> (istream &is, vector> &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } // output template ostream& operator << (ostream &s, const pair &P) { return s << '<' << P.first << ", " << P.second << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; } template ostream& operator << (ostream &s, const vector &P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, const deque &P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, const vector> &P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template ostream& operator << (ostream &s, const set &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const multiset &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const unordered_set &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const map &P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } template ostream& operator << (ostream &s, const unordered_map &P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } void yes(bool a) { cout << (a ? "yes" : "no") << endl; } void YES(bool a) { cout << (a ? "YES" : "NO") << endl; } void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; } const vector DX = {1, 0, -1, 0, 1, -1, 1, -1}; const vector DY = {0, 1, 0, -1, 1, -1, -1, 1}; // 1, 2, 3-variable submodular optimization template struct ThreeVariableSubmodularOpt { // constructors ThreeVariableSubmodularOpt() : N(2), S(0), T(0), OFFSET(0) {} ThreeVariableSubmodularOpt(int n, COST inf = numeric_limits::max() / 2) : N(n), S(n), T(n + 1), OFFSET(0), INF(inf), list(n + 2) {} // initializer void init(int n, COST inf = numeric_limits::max() / 2) { N = n, S = n, T = n + 1; OFFSET = 0, INF = inf; list.clear(); list.resize(N + 2); pos.clear(); } // add constant cost void add_cost(COST cost) { OFFSET += cost; } // add 1-variable submodular function void add_single_cost(int xi, COST false_cost, COST true_cost) { assert(0 <= xi && xi < N); if (false_cost >= true_cost) { OFFSET += true_cost; add_edge(S, xi, false_cost - true_cost); } else { OFFSET += false_cost; add_edge(xi, T, true_cost - false_cost); } } void add_single_cost_01(int xi, COST false_cost, COST true_cost) { add_single_cost(xi, false_cost, true_cost); } // add "project selection" constraint // xi = T, xj = F: strictly prohibited void add_psp_constraint(int xi, int xj) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); add_edge(xi, xj, INF); } void add_psp_constraint_01(int xi, int xj) { add_psp_constraint(xj, xi); } void add_psp_constraint_10(int xi, int xj) { add_psp_constraint(xi, xj); } // add "project selection" penalty // xi = T, xj = F: cost C void add_psp_penalty(int xi, int xj, COST C) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(C >= 0); add_edge(xi, xj, C); } void add_psp_penalty_01(int xi, int xj, COST C) { add_psp_penalty(xj, xi, C); } void add_psp_penalty_10(int xi, int xj, COST C) { add_psp_penalty(xi, xj, C); } // add both True profit // xi = T, xj = T: profit P (cost -P) void add_both_true_profit(int xi, int xj, COST P) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(P >= 0); OFFSET -= P; add_edge(S, xi, P); add_edge(xi, xj, P); } // add both False profit // xi = F, xj = F: profit P (cost -P) void add_both_false_profit(int xi, int xj, COST P) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(P >= 0); OFFSET -= P; add_edge(xj, T, P); add_edge(xi, xj, P); } // add general 2-variable submodular function // (xi, xj) = (F, F): A, (F, T): B // (xi, xj) = (T, F): C, (T, T): D void add_submodular_function(int xi, int xj, COST A, COST B, COST C, COST D) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(B + C >= A + D); // assure submodular function OFFSET += A; add_single_cost(xi, 0, D - B); add_single_cost(xj, 0, B - A); add_psp_penalty(xi, xj, B + C - A - D); } // add all True profit // y = F: not gain profit (= cost is P), T: gain profit (= cost is 0) // y: T, xi: F is prohibited void add_all_true_profit(const vector &xs, COST P) { assert(P >= 0); int y = (int)list.size(); list.resize(y + 1); OFFSET -= P; add_edge(S, y, P); for (auto xi : xs) { assert(xi >= 0 && xi < N); add_edge(y, xi, INF); } } // add all False profit // y = F: gain profit (= cost is 0), T: not gain profit (= cost is P) // xi = T, y = F is prohibited void add_all_false_profit(const vector &xs, COST P) { assert(P >= 0); int y = (int)list.size(); list.resize(y + 1); OFFSET -= P; add_edge(y, T, P); for (auto xi : xs) { assert(xi >= 0 && xi < N); add_edge(xi, y, INF); } } // add general 3-variable submodular function // (xi, xj, xk) = (F, F, F): cost A // (xi, xj, xk) = (F, F, T): cost B // (xi, xj, xk) = (F, T, F): cost C // (xi, xj, xk) = (F, T, T): cost D // (xi, xj, xk) = (T, F, F): cost E // (xi, xj, xk) = (T, F, T): cost F // (xi, xj, xk) = (T, T, F): cost G // (xi, xj, xk) = (T, T, T): cost H void add_submodular_function(int xi, int xj, int xk, COST A, COST B, COST C, COST D, COST E, COST F, COST G, COST H) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(0 <= xk && xk < N); COST P = (A + D + F + G) - (B + C + E + H); COST P12 = (C + E) - (A + G), P13 = (D + G) - (C + H); COST P21 = (D + F) - (B + H), P23 = (B + C) - (A + D); COST P31 = (B + E) - (A + F), P32 = (F + G) - (E + H); assert(P12 >= 0 && P21 >= 0); assert(P23 >= 0 && P32 >= 0); assert(P31 >= 0 && P13 >= 0); if (P >= 0) { OFFSET += A; add_single_cost(xi, 0, F - B); add_single_cost(xj, 0, G - E); add_single_cost(xk, 0, D - C); add_psp_penalty(xj, xi, P12); add_psp_penalty(xk, xj, P23); add_psp_penalty(xi, xk, P31); add_all_true_profit({xi, xj, xk}, P); } else { OFFSET += H; add_single_cost(xi, C - G, 0); add_single_cost(xj, B - D, 0); add_single_cost(xk, E - F, 0); add_psp_penalty(xi, xj, P21); add_psp_penalty(xj, xk, P32); add_psp_penalty(xk, xi, P13); add_all_false_profit({xi, xj, xk}, -P); } } // solve COST solve() { return dinic() + OFFSET; } // reconstrcut the optimal assignment vector reconstruct() { vector res(N, false), seen(list.size(), false); queue que; seen[S] = true; que.push(S); while (!que.empty()) { int v = que.front(); que.pop(); for (const auto &e : list[v]) { if (e.cap && !seen[e.to]) { if (e.to < N) res[e.to] = true; seen[e.to] = true; que.push(e.to); } } } return res; } // debug friend ostream& operator << (ostream& s, const ThreeVariableSubmodularOpt &tvs) { const auto &edges = tvs.get_edges(); for (const auto &e : edges) s << e << endl; return s; } private: // edge class struct Edge { // core members int rev, from, to; COST cap, icap, flow; // constructor Edge(int r, int f, int t, COST c) : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {} void reset() { cap = icap, flow = 0; } // debug friend ostream& operator << (ostream& s, const Edge& E) { return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')'; } }; // inner data int N, S, T; COST OFFSET, INF; vector> list; vector> pos; // add edge Edge &get_rev_edge(const Edge &e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } Edge &get_edge(int i) { return list[pos[i].first][pos[i].second]; } const Edge &get_edge(int i) const { return list[pos[i].first][pos[i].second]; } vector get_edges() const { vector edges; for (int i = 0; i < (int)pos.size(); ++i) { edges.push_back(get_edge(i)); } return edges; } void add_edge(int from, int to, COST cap) { if (!cap) return; pos.emplace_back(from, (int)list[from].size()); list[from].push_back(Edge((int)list[to].size(), from, to, cap)); list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0)); } // Dinic's algorithm COST dinic(COST limit_flow) { COST current_flow = 0; vector level((int)list.size(), -1), iter((int)list.size(), 0); // Dinic BFS auto bfs = [&]() -> void { level.assign((int)list.size(), -1); level[S] = 0; queue que; que.push(S); while (!que.empty()) { int v = que.front(); que.pop(); for (const Edge &e : list[v]) { if (level[e.to] < 0 && e.cap > 0) { level[e.to] = level[v] + 1; if (e.to == T) return; que.push(e.to); } } } }; // Dinic DFS auto dfs = [&](auto self, int v, COST up_flow) { if (v == T) return up_flow; COST res_flow = 0; for (int &i = iter[v]; i < (int)list[v].size(); ++i) { Edge &e = list[v][i], &re = get_rev_edge(e); if (level[v] >= level[e.to] || e.cap == 0) continue; COST flow = self(self, e.to, min(up_flow - res_flow, e.cap)); if (flow <= 0) continue; res_flow += flow; e.cap -= flow, e.flow += flow; re.cap += flow, re.flow -= flow; if (res_flow == up_flow) break; } return res_flow; }; // flow while (current_flow < limit_flow) { bfs(); if (level[T] < 0) break; iter.assign((int)iter.size(), 0); while (current_flow < limit_flow) { COST flow = dfs(dfs, S, limit_flow - current_flow); if (!flow) break; current_flow += flow; } } return current_flow; }; COST dinic() { return dinic(numeric_limits::max() / 2); } }; // K-value Two Variable Monge Function Optimization /* X[i] = 0, 1, ..., K-1 -> (x[i][1], ..., x[i][K-1]) X[i] < d -> x[i][d] = 1 X[i] = d -> x[i][1] = 0, ..., x[i][d] = 0, x[i][d+1] = 1, ..., x[i][K] = 1 X[i] = 0 -> (1, 1, 1, ..., 1, 1) X[i] = 1 -> (0, 1, 1, ..., 1, 1) X[i] = 2 -> (0, 0, 1, ..., 1, 1) ... X[i] = K-2 -> (0, 0, 0, ..., 0, 1) X[i] = K-1 -> (0, 0, 0, ..., 0, 0) */ template struct TwoVariableMongeOpt { // inner data int N, N01; COST INF; vector ks; // size of x[i] vector> x; // index of x[i][k] in normal submodular optimization ThreeVariableSubmodularOpt tvs; // constructors TwoVariableMongeOpt() {} TwoVariableMongeOpt(int N, int K, COST inf = numeric_limits::max() / 2) { vector ks(N, K); init(ks, inf); } TwoVariableMongeOpt(const vector &ks, COST inf = numeric_limits::max() / 2) { init(ks, inf); } void init(const vector &iks, COST inf = numeric_limits::max() / 2) { N = (int)iks.size(), INF = inf, ks = iks, N01 = 0; x.resize(N); for (int i = 0; i < N; i++) { assert(ks[i] >= 2); x[i].assign(ks[i], 0); for (int k = 1; k < ks[i]; k++) x[i][k] = N01++; } tvs.init(N01, INF); for (int i = 0; i < N; i++) { for (int k = 1; k < ks[i] - 1; k++) { tvs.add_psp_constraint(x[i][k], x[i][k + 1]); } } } // add constant cost void add_cost(COST cost) { tvs.add_cost(cost); } // add 1-variable function void add_single_cost(int xi, const vector &cost) { assert(0 <= xi && xi < N); assert((int)cost.size() == ks[xi]); tvs.add_cost(cost[ks[xi] - 1]); for (int k = 1; k < ks[xi]; k++) { tvs.add_single_cost(x[xi][k], 0, cost[k-1] - cost[k]); } } // add 2-variable Monge function // cost[i][j]+cost[i+1][j+1] <= cost[i+1][j]+cost[i][j+1] void add_monge_function(int xi, int xj, vector> cost) { assert(0 <= xi && xi < N); assert(0 <= xj && xj < N); assert(xi != xj); assert(cost.size() == ks[xi]); assert(cost[0].size() == ks[xj]); vector icost(ks[xi]), jcost(ks[xj]); for (int ki = 0; ki < ks[xi]; ki++) { icost[ki] = cost[ki][0]; for (int kj = 0; kj < ks[xj]; kj++) cost[ki][kj] -= icost[ki]; } for (int kj = 0; kj < ks[xj]; kj++) { jcost[kj] = cost[0][kj]; for (int ki = 0; ki < ks[xi]; ki++) cost[ki][kj] -= jcost[kj]; } add_single_cost(xi, icost), add_single_cost(xj, jcost); for (int ki = 1; ki < ks[xi]; ki++) { for (int kj = 1; kj < ks[xj]; kj++) { COST c = cost[ki][kj] - cost[ki][kj-1] - cost[ki-1][kj] + cost[ki-1][kj-1]; assert(c <= 0); tvs.add_both_false_profit(x[xi][ki], x[xj][kj], -c); } } } // solve COST solve() { return tvs.solve(); } // reconstrcut the optimal assignment vector reconstruct() { vector res(N, 0); vector tres = tvs.reconstruct(); for (int i = 0; i < N; i++) for (int ki = 1; ki < ks[i]; ki++) { res[i] += not tres[x[i][ki]]; } return res; } }; //------------------------------// // Solver //------------------------------// /* 0: 行くけどツアーに参加しない(-C[i]) 1: 行かない(0) 2: 行ってツアーにも参加する(-B[i]) (x, y) に対して x/y 0 1 2 0 0 0 0 1 0 0 0 2 INF 0 0 */ int main() { ll N, M; cin >> N >> M; vll A(N), B(M); cin >> A >> B; vvint C(M); REP(i, M) { ll K; cin >> K; C[i].resize(K); REP(j, K) cin >> C[i][j], C[i][j]--; } ThreeVariableSubmodularOpt opt(N); REP(i, N) opt.add_single_cost(i, 0, A[i]); REP(i, M) opt.add_all_true_profit(C[i], B[i]); auto res = -opt.solve(); cout << res << endl; }