#include using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; #define fst first #define snd second #define all(c) ((c).begin()), ((c).end()) const long long INF = (1ll << 50); struct graph { typedef long long flow_type; struct edge { int src, dst; flow_type capacity, flow; size_t rev; }; int n; vector> adj; graph(int n) : n(n), adj(n) { } void add_edge(int src, int dst, ll capacity) { adj[src].push_back({src, dst, capacity, 0, adj[dst].size()}); adj[dst].push_back({dst, src, 0, 0, adj[src].size() - 1}); } flow_type max_flow(int s, int t) { vector excess(n); vector dist(n), active(n), count(2*n); queue Q; auto enqueue = [&](int v) { if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } }; auto push = [&](edge &e) { flow_type f = min(excess[e.src], e.capacity - e.flow); if (dist[e.src] <= dist[e.dst] || f == 0) return; e.flow += f; adj[e.dst][e.rev].flow -= f; excess[e.dst] += f; excess[e.src] -= f; enqueue(e.dst); }; dist[s] = n; active[s] = active[t] = true; count[0] = n-1; count[n] = 1; for (int u = 0; u < n; ++u) for (auto &e: adj[u]) e.flow = 0; for (auto &e: adj[s]) { excess[s] += e.capacity; push(e); } while (!Q.empty()) { int u = Q.front(); Q.pop(); active[u] = false; for (auto &e: adj[u]) push(e); if (excess[u] > 0) { if (count[dist[u]] == 1) { int k = dist[u]; // Gap Heuristics for (int v = 0; v < n; v++) { if (dist[v] < k) continue; count[dist[v]]--; dist[v] = max(dist[v], n+1); count[dist[v]]++; enqueue(v); } } else { count[dist[u]]--; // Relabel dist[u] = 2*n; for (auto &e: adj[u]) if (e.capacity > e.flow) dist[u] = min(dist[u], dist[e.dst] + 1); count[dist[u]]++; enqueue(u); } } } flow_type flow = 0; for (auto e: adj[s]) flow += e.flow; return flow; } }; ll A[303][303]; ll R[303]; ll C[303]; void solve() { int H, W; cin >> H >> W; REP(i, H) REP(j, W) cin >> A[i][j]; REP(i, H) cin >> R[i]; REP(j, W) cin >> C[j]; graph g(H+W+2); int source = H + W; int sink = H + W + 1; REP(i, H) { ll s = 0; REP(j, W) s += A[i][j]; g.add_edge(source, i, s); g.add_edge(i, sink, R[i]); } REP(j, W) { g.add_edge(H+j, sink, C[j]); } REP(i, H) REP(j, W) { g.add_edge(i, H+j, A[i][j]); } ll ans = 0; REP(i, H) ans += R[i]; REP(j, W) ans += C[j]; ans -= g.max_flow(source, sink); cout << ans << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); solve(); }