#include #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef tuple t3; typedef tuple t4; #define rep(a,n) for(ll a = 0;a < n;a++) #define repi(a,b,n) for(ll a = b;a < n;a++) template void chmax(T& reference, T value) { reference = max(reference, value); } template void chmaxmap(map& m, T key, T value) { if (m.count(key)) { chmax(m[key], value); } else { m[key] = value; } } template void chmin(T& reference, T value) { reference = min(reference, value); } template< typename G > struct HeavyLightDecomposition { G& g; vector< int > sz, in, out, head, rev, par; HeavyLightDecomposition(G& g) : g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {} void dfs_sz(int idx, int p) { par[idx] = p; sz[idx] = 1; if (g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back()); for (auto& to : g[idx]) { if (to == p) continue; dfs_sz(to, idx); sz[idx] += sz[to]; if (sz[g[idx][0]] < sz[to]) swap(g[idx][0], to); } } void dfs_hld(int idx, int par, int& times) { in[idx] = times++; rev[in[idx]] = idx; for (auto& to : g[idx]) { if (to == par) continue; head[to] = (g[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } void build() { dfs_sz(0, -1); int t = 0; dfs_hld(0, -1, t); } int la(int v, int k) { while (1) { int u = head[v]; if (in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; } } template< typename T, typename Q, typename F > T query(int u, int v, const T& ti, const Q& q, const F& f, bool edge = false) { T l = ti, r = ti; for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v), swap(l, r); if (head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return f(f(q(in[u] + edge, in[v] + 1), l), r); } template< typename Q > void add(int u, int v, const Q& q, bool edge = false) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } }; typedef vector> UnWeightedGraph; class lca { public: typedef vector> Graph; const int n; const int log2_n; std::vector> parent; std::vector depth; lca(const Graph& g, int root) : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector(n)), depth(n) { dfs(g, root, -1, 0); for (int k = 0; k + 1 < log2_n; k++) { for (int v = 0; v < (int)g.size(); v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } void dfs(const Graph& g, int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int j = 0; j < g[v].size(); j++) { if (g[v][j] != p) dfs(g, g[v][j], v, d + 1); } } int get(int u, int v) { if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < log2_n; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = log2_n - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[get(u, v)]; } }; namespace { using namespace std; template< typename G > struct LowLink { const G& g; vector< int > used, ord, low; vector< int > articulation; vector< pair< int, int > > bridge; LowLink(const G& g) : g(g) {} int dfs(int idx, int k, int par) { used[idx] = true; ord[idx] = k++; low[idx] = ord[idx]; bool is_articulation = false; int cnt = 0; for (auto& to : g[idx]) { if (!used[to]) { ++cnt; k = dfs(to, k, idx); low[idx] = min(low[idx], low[to]); is_articulation |= ~par && low[to] >= ord[idx]; if (ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int)to)); } else if (to != par) { low[idx] = min(low[idx], ord[to]); } } is_articulation |= par == -1 && cnt > 1; if (is_articulation) articulation.push_back(idx); return k; } virtual void build() { used.assign(g.size(), 0); ord.assign(g.size(), 0); low.assign(g.size(), 0); int k = 0; for (int i = 0; i < g.size(); i++) { if (!used[i]) k = dfs(i, k, -1); } } }; template< typename G > struct TwoEdgeConnectedComponents { vector< int > comp; LowLink< G > lowLink_; TwoEdgeConnectedComponents(const G& g) : lowLink_(g) {} int operator[](const int& k) { return comp[k]; } void dfs(int idx, int par, int& k) { if (~par && lowLink_.ord[par] >= lowLink_.low[idx]) comp[idx] = comp[par]; else comp[idx] = k++; for (auto& to : lowLink_.g[idx]) { if (comp[to] == -1) dfs(to, idx, k); } } typedef std::vector> UnWeightedGraph; void build(UnWeightedGraph& t) { lowLink_.build(); comp.assign(lowLink_.g.size(), -1); int k = 0; for (int i = 0; i < comp.size(); i++) { if (comp[i] == -1) dfs(i, -1, k); } t.resize(k); for (auto& e : lowLink_.bridge) { int x = comp[e.first], y = comp[e.second]; t[x].push_back(y); t[y].push_back(x); } } }; } class Primes { public: vector Prime_Number; vector is_prime_; Primes(int N) { is_prime_.resize(N + 1, true); is_prime_[0] = is_prime_[1] = false; for (int i = 0; i < N + 1; i++) { if (is_prime_[i]) { Prime_Number.push_back(i); for (int j = 2 * i; j <= N; j += i) is_prime_[j] = false; } } } int operator[](int i) { return Prime_Number[i]; } int size() { return Prime_Number.size(); } int back() { return Prime_Number.back(); } bool isPrime(int q) { return is_prime_[q]; } }; #include using namespace atcoder; typedef modint1000000007 mint; #pragma once #include template< class T > struct Matrix { vector< vector< T > > A; Matrix() {} Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {} Matrix(size_t n) : A(n, vector< T >(n, 0)) {}; size_t height() const { return (A.size()); } int size() const { return A.size(); } size_t width() const { return (A[0].size()); } inline const vector< T >& operator[](int k) const { return (A.at(k)); } inline vector< T >& operator[](int k) { return (A.at(k)); } static Matrix Identity(size_t n) { Matrix mat(n); for (int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix& operator+=(const Matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix& operator-=(const Matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix& operator*=(const Matrix& B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); vector< vector< T > > C(n, vector< T >(m, 0)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]); A.swap(C); return (*this); } Matrix& operator^=(long long k) { Matrix B = Matrix::I(height()); while (k > 0) { if (k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix& B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix& B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix& B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } friend ostream& operator<<(ostream& os, Matrix& p) { size_t n = p.height(), m = p.width(); for (int i = 0; i < n; i++) { os << "["; for (int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return (os); } T determinant() { Matrix B(*this); assert(width() == height()); T ret = 1; for (int i = 0; i < width(); i++) { int idx = -1; for (int j = i; j < width(); j++) { if (B[j][i] != 0) idx = j; } if (idx == -1) return (0); if (i != idx) { ret *= -1; swap(B[i], B[idx]); } ret *= B[i][i]; T vv = B[i][i]; for (int j = 0; j < width(); j++) { B[i][j] /= vv; } for (int j = i + 1; j < width(); j++) { T a = B[j][i]; for (int k = 0; k < width(); k++) { B[j][k] -= B[i][k] * a; } } } return (ret); } }; namespace { using namespace std; static constexpr double EPS = 0; template static int GaussJordan(Matrix& A, bool is_extended = false) { int m = A.size(), n = A[0].size(); int rank = 0; for (int col = 0; col < n; ++col) { // 拡大係数行列の場合は最後の列は掃き出ししない if (is_extended && col == n - 1) break; // ピボットを探す int pivot = -1; T ma = 0; for (int row = rank; row < m; ++row) { if (abs(A[row][col]) > ma) { ma = abs(A[row][col]); pivot = row; break; } } // ピボットがなかったら次の列へ if (pivot == -1) continue; // まずは行を swap swap(A[pivot], A[rank]); // ピボットのある列の値がすべて 0 になるように掃き出す for (int row = 0; row < m; ++row) { //bitが立っている if (row != rank && A[row][col]) { for (int col2 = 0; col2 < n; ++col2) { A[row][col2] ^= A[rank][col2]; } } } ++rank; } return rank; } //誤差に注意 template static std::vector linear_equation(const Matrix& A, std::vector b) { // extended int m = A.size(), n = A[0].size(); Matrix M(m, n + 1); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) M[i][j] = A[i][j]; M[i][n] = b[i]; } int rank = GaussJordan(M, true); // check if it has no solution vector res; for (int row = rank; row < m; ++row) if (abs(M[row][n]) > EPS) return res; // answer res.assign(n, 0); for (int i = 0; i < rank; ++i) res[i] = M[i][n]; return res; } template void linear_equation_gauss_seidel( const Matrix& a, const std::vector& b, std::vector& x, int iteration) { std::vector buffer = x; rep(_, iteration) { int rows = a.size(); int cols = a[0].size(); for (int y = 0; y < rows; y++) { T sum = 0; for (int j = 0; j < cols; j++) { if (y != j) { sum += a[y][j] * x[j]; } } T c = (b[y] - sum); T next = c / a[y][y]; buffer[y] = next; } swap(x, buffer); } } template void linear_equation_gauss_seidel_sparse( const vector>>& a, const std::vector& b, std::vector& x, int iteration) { std::vector buffer = x; rep(_, iteration) { int rows = a.size(); int cols = a[0].size(); for (int y = 0; y < rows; y++) { T sum = 0; T diag = 0; for (auto p : a[y]) { int j = p.first; T value = p.second; if (y != j) { sum += value * x[j]; } else { diag = value; } } T c = (b[y] - sum); T next = c / diag; buffer[y] = next; } swap(x, buffer); } } } using S = long long; using F = long long; const S INF = 8e18; const F ID = -8e18; constexpr ll mod = 1000000007; constexpr ll mpow(ll x, ll n) { ll ans = 1; x %= mod; while (n != 0) { if (n & 1) ans = ans * x % mod; x = x * x % mod; n = n >> 1; } return ans; } constexpr ll inv_mod(ll a) { return mpow(a, mod - 2); } class Factorial { private: vector fac; vector ifac; public: Factorial(ll N) { fac.push_back(1); for (int i = 0; i < N; i++) fac.push_back(fac[i] * (i + 1) % mod); ifac.resize(N + 1); ifac[N] = inv_mod(fac[N]); for (int i = 0; i < N; i++) ifac[N - 1 - i] = (ifac[N - i] * (N - i)) % mod; } ll fact(ll a) { return fac[a]; } ll ifact(ll a) { return ifac[a]; } ll cmb(ll a, ll b) { if (a == 0 && b == 0) return 1; if (a < b || a < 0 || b < 0) return 0; ll tmp = ifact(a - b) * ifact(b) % mod; return tmp * fac[a] % mod; } ll per(ll a, ll b) { if (a == 0 && b == 0) return 1; if (a < b || a < 0 || b < 0) return 0; return fac[a] * ifac[a - b] % mod; } }; typedef modint1000000007 mint; int main() { int h, w; cin >> h >> w; atcoder::mf_graph g(h * w + h + w + 2); int s = h * w + h + w; int goal = s + 1; rep(i, h) { rep(j, w) { ll x; cin >> x; int id = i * w + j; g.add_edge(s, id, x); } } ll sum = 0; rep(i, h) { ll x; cin >> x; sum += x; int id = h * w + i; g.add_edge(id, goal, x); rep(j, w) { g.add_edge(i * w + j, id, 1e15); } } rep(j, w) { ll x; cin >> x; sum += x; int id = h * w + h + j; g.add_edge(id, goal, x); rep(i, h) { g.add_edge(i * w + j, id, 1e15); } } sum -= g.flow(s, goal); cout << sum << endl; return 0; }