#include #pragma GCC optimize("O3", "unroll-loops") #pragma GCC target("avx") using namespace std; using lint = long long int; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template istream &operator>>(istream &is, vector &vec){ for (auto &v : vec) is >> v; return is; } ///// This part below is only for debug, not used ///// template ostream &operator<<(ostream &os, const vector &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const pair &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; ///// END ///// class Maxflow { using T = lint; struct edge { int to; T cap; int rev; }; std::vector > edges; std::vector level; std::vector iter; void bfs(int s) { level = std::vector(edges.size(), -1); std::queue q; level[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (edge &e : edges[v]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } T dfs_d(int v, int goal, T f) { if (v == goal) return f; for (int &i = iter[v]; i < (int)edges[v].size(); i++) { edge &e = edges[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { T d = dfs_d(e.to, goal, std::min(f, e.cap)); if (d > 0) { e.cap -= d; edges[e.to][e.rev].cap += d; return d; } } } return 0; } public: Maxflow(int N) { edges.resize(N); } void add_edge(int from, int to, T capacity) { edges[from].push_back(edge{to, capacity, (int)edges[to].size()}); edges[to].push_back(edge{from, (T)0, (int)edges[from].size() - 1}); } T Dinic(int s, int t) { constexpr T INF = std::numeric_limits::max(); T flow = 0; while (true) { bfs(s); if (level[t] < 0) return flow; iter = std::vector(edges.size(), 0); T f; while ((f = dfs_d(s, t, INF)) > 0) flow += f; } } }; int main() { int H, W; cin >> H >> W; vector> G(H, vector(W)); cin >> G; vector R(H), C(W); cin >> R >> C; lint tot = accumulate(ALL(R), 0LL) + accumulate(ALL(C), 0LL); vector EW(W); lint f1 = 0; int Z = 1 + H + W; Maxflow g(Z + 1); REP(i, H) { lint gtot = accumulate(ALL(G[i]), 0LL); lint f0 = min(gtot, R[i]); f1 += f0; g.add_edge(0, i + 1, gtot - f0); } REP(j, W) g.add_edge(H + 1 + j, Z, C[j]); REP(i, H) REP(j, W) g.add_edge(i + 1, H + 1 + j, G[i][j]); lint f2 = g.Dinic(0, Z); cout << tot - f1 - f2 << endl; }