// 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 /* N 個の bool 変数 x_0, x_1, ..., x_{N-1} について、以下の形のコストが定められたときの最小コストを求める ・1 変数 xi に関するコスト (1 変数劣モジュラ関数) xi = F のときのコスト, xi = T のときのコスト ・2 変数 xi, xj 間の関係性についてのコスト (2 変数劣モジュラ関数)   (xi, xj) = (F, F): コスト A   (xi, xj) = (F, T): コスト B   (xi, xj) = (T, F): コスト C   (xi, xj) = (T, T): コスト D  (ただし、B + C >= A + D でなければならない) ・よくある例は、A = B = D = 0, C >= 0 の形である (特に関数化している) ・この場合は、特に Project Selection Problem と呼ばれ、俗に「燃やす埋める」などとも呼ばれる ・xi = T, xj = F のときにコスト C がかかる ・他に面白い例として、A = B = C = 0, D <= 0 の形もある (これも関数化している) ・xi = T, xj = T のときに (-D) の利得が得られる ・3 変数 xi, xj, xk 間の関係性についてのコスト (3 変数劣モジュラ関数)   (xi, xj, xk) = (F, F, F): コスト A   (xi, xj, xk) = (F, F, T): コスト B   (xi, xj, xk) = (F, T, F): コスト C   (xi, xj, xk) = (F, T, T): コスト D   (xi, xj, xk) = (T, F, F): コスト E   (xi, xj, xk) = (T, F, T): コスト F   (xi, xj, xk) = (T, T, F): コスト G   (xi, xj, xk) = (T, T, T): コスト H */ // 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; if (false_cost - true_cost > 0) 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); } void add_single_cost_10(int xi, COST false_cost, COST true_cost) { add_single_cost(xi, true_cost, false_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); assert(xi != xj); 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(xi != xj); assert(C >= 0); if (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(xi != xj); assert(P >= 0); OFFSET -= P; if (P > 0) add_edge(S, xi, P); if (P > 0) 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(xi != xj); assert(P >= 0); OFFSET -= P; if (P > 0) add_edge(xj, T, P); if (P > 0) 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(xi != xj); assert(B + C >= A + D); // assure submodular function OFFSET += A; add_single_cost(xi, 0, D - B); add_single_cost(xj, 0, B - A); if (B + C - A - D > 0) 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 > 0 && !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; // constructor Edge(int r, int f, int t, COST c) : rev(r), from(f), to(t), cap(c) {} // debug friend ostream& operator << (ostream& s, const Edge& e) { return s << e.from << "->" << e.to << '(' << e.cap << ')'; } }; // inner data int N, S, T; COST OFFSET, INF; vector> list; vector> pos; // add edge Edge &get_rev_edge(const Edge &e) { return list[e.to][e.rev]; } 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 <= 0) 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); queue que; // Dinic BFS auto bfs = [&]() -> void { fill(level.begin(), level.end(), -1); level[S] = 0; while (!que.empty()) que.pop(); 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 == S) 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] || re.cap <= 0) continue; COST flow = self(self, e.to, min(up_flow - res_flow, re.cap)); if (flow <= 0) continue; res_flow += flow; e.cap += flow, re.cap -= flow; if (res_flow == up_flow) return res_flow; } level[v] = (int)list.size(); return res_flow; }; // flow while (current_flow < limit_flow) { bfs(); if (level[T] < 0) break; fill(iter.begin(), iter.end(), 0); while (current_flow < limit_flow) { COST flow = dfs(dfs, T, limit_flow - current_flow); if (flow <= 0) break; current_flow += flow; } } return current_flow; }; COST dinic() { return dinic(numeric_limits::max() / 2); } }; //------------------------------// // Solver //------------------------------// int main() { ll H, W; cin >> H >> W; vvll G(H, vll(W)); vll R(H), C(W); cin >> G >> R >> C; ThreeVariableSubmodularOpt opt(H * W); REP(i, H) REP(j, W) opt.add_single_cost_10(i*W+j, G[i][j], 0); REP(i, H) { vint ids; REP(j, W) ids.EB(i*W+j); opt.add_all_true_profit(ids, R[i]); } REP(j, W) { vint ids; REP(i, H) ids.EB(i*W+j); opt.add_all_true_profit(ids, C[j]); } cout << -opt.solve() << endl; }