#include 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 SZ(x) ((lint)(x).size()) #define POW2(n) (1LL << (n)) #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 void ndarray(vector &vec, int len) { vec.resize(len); } template void ndarray(vector &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); } template bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; } template bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } template pair operator+(const pair &l, const pair &r) { return make_pair(l.first + r.first, l.second + r.second); } template pair operator-(const pair &l, const pair &r) { return make_pair(l.first - r.first, l.second - r.second); } 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 deque &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &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; } template ostream &operator<<(ostream &os, const map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; ///// END ///// #define int long long // #define N 300*300 + 600 + 2 + 10 class PushRelabel { const int inf = 1e9; int n; struct Edge { int to, cap, rev; }; vector g[N]; int qs[N]; int hs[N], ds[N], fs[N]; bool active[N]; vector bs[N]; int cur; public: PushRelabel() {} PushRelabel(int n) { init(n); } inline void init(int n) { this->n = n; } inline void add_edge(int fr, int to, int cap) { g[fr].emplace_back(Edge{to, cap, (int) g[to].size()}); g[to].emplace_back(Edge{fr, 0, (int) g[fr].size()-1}); } inline int bfs(int t) { int a = 0, b = 1; for(int i=0; i= 0 && bs[cur].size() == 0) --cur; if(cur < 0) break; int v = bs[cur].back(); bs[cur].pop_back(); if(v == t) continue; int hv = hs[v]; // Gap-relabeling if(hv > gap) { if(hv < n) --ds[hv]; hs[v] = n; continue; } // push int rest = fs[v]; for(Edge &e : g[v]) { int w = e.to; if(e.cap > 0 && hv > hs[w] && hs[w] < gap) { int d = min(rest, e.cap); e.cap -= d; g[w][e.rev].cap += d; rest -= d; fs[w] += d; if(!active[w]) { int hw = hs[w]; bs[hw].push_back(w); if(cur < hw) cur = hw; active[w] = true; } if(rest == 0) break; } } fs[v] = rest; if(rest == 0) { active[v] = false; continue; } // relabel int h0 = hs[v]; hv = n; for(Edge &e : g[v]) { int w = e.to; if(e.cap > 0 && hv > hs[w] + 1 && hs[w] < gap) { hv = hs[w] + 1; } } if(h0 != hv) { --ds[h0]; if(ds[h0] == 0 && h0 < gap) { gap = h0; hv = n; } else if(hv == gap) { ++gap; } if(hv < n) ++ds[hv]; } hs[v] = hv; if(hv < n) { bs[hv].push_back(v); if(cur < hv) cur = hv; } else { active[v] = false; } if((++cnt) % n == 0) { gap = bfs(t); } } return fs[t]; } }; PushRelabel g; signed main() { int H, W; cin >> H >> W; vector> G(H, vector(W)); cin >> G; vector R(H), C(W); cin >> R >> C; int Z = 1 + H + W + H * W; g.init(Z + 1); REP(i, H) if (R[i]) g.add_edge(0, i + 1,R[i]); REP(j, W) if (C[j]) g.add_edge(0, H + 1 + j, C[j]); REP(i, H) REP(j, W) { int b = H + W + 1 + i * W + j; if (G[i][j] < R[i] + C[j]) { g.add_edge(i + 1, b, 1e10); g.add_edge(H + 1 + j, b, 1e10); g.add_edge(b, Z, G[i][j]); } else { g.add_edge(i + 1, Z, 1e10); g.add_edge(H + j + 1, Z, 1e10); } } lint f = g.flow(0, Z); cout << accumulate(ALL(R), 0LL) + accumulate(ALL(C), 0LL) - f << endl; }