#include #include #include using namespace std; #define PB push_back constexpr int kN = int(1E5 + 10), kNN = int(3E2 + 10); constexpr long long int kInf = (long long int) (1E16 + 10); struct Edge { int to, rev; long long int cap; }; vector graph[kN]; int dep[kN], went[kN], iter[kN]; void AddEdge(int u, int v, long long int c) { graph[u].PB({v, int(graph[v].size()), c}); graph[v].PB({u, int(graph[u].size()) - 1, 0}); return ; } void bfs(int s, int t) { int nxt; queue q; q.push(s); iter[s] = dep[s] = 0; went[s] = t; while (!q.empty()) { nxt = q.front(); q.pop(); for (Edge i : graph[nxt]) if (went[i.to] != t && i.cap > 0) { q.push(i.to); went[i.to] = t; dep[i.to] = dep[nxt] + 1; iter[i.to] = 0; } } return ; } long long int dfs(int u, int t, long long int nv) { if (u == t) return nv; int temp; for (int &i = iter[u]; i < int(graph[u].size()); i++) { Edge& nxt = graph[u][i]; if (nxt.cap > 0 && dep[nxt.to] > dep[u]) { temp = dfs(nxt.to, t, min(nv, nxt.cap)); if (temp > 0) { nxt.cap -= temp; graph[nxt.to][nxt.rev].cap += temp; return temp; } } } return 0; } long long int dinic(int s, int t) { long long int ans = 0, f; int cnt = 0; for (int i = 0; i < kN; i++) went[i] = cnt; while (true) { bfs(s, ++cnt); if (went[s] != went[t]) break; while ((f = dfs(s, t, kInf)) > 0) ans += f; } return ans; } long long int a[kNN], g[kNN][kNN], r[kNN], c[kNN]; int main() { int n, m, s, t; long long int ans = 0, tmp; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%lld", &g[i][j]); for (int i = 1; i <= n; i++) scanf("%lld", &r[i]); for (int i = 1; i <= m; i++) scanf("%lld", &c[i]); s = 0; t = n + m + 1; for (int i = 1; i <= n; i++) a[i] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i] += g[i][j]; for (int i = 1; i <= n; i++) { tmp = min(r[i], a[i]); r[i] -= tmp; a[i] -= tmp; } for (int i = 1; i <= n; i++) ans += r[i]; for (int i = 1; i <= m; i++) ans += c[i]; for (int i = 1; i <= n; i++) AddEdge(s, i, a[i]); for (int i = 1; i <= m; i++) AddEdge(i + n, t, c[i]); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) AddEdge(i, j + n, g[i][j]); printf("%lld\n", ans - dinic(s, t)); }