#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++) #include using namespace std; 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); } #include using namespace atcoder; struct MaxFlowCalculator { typedef ll flow_type; //g.first...cost //g.second..dest int max_flow(int s, int t, const vector>>& g) { struct edge_ { flow_type to, cap, rev; }; vector used(g.size(), false); vector> G(g.size()); for (int i = 0; i < g.size(); i++) for (int j = 0; j < g[i].size(); j++) { int from = i, to = g[i][j].second; flow_type cap = g[i][j].first; G[from].push_back({ to, cap, (flow_type)G[to].size() }); G[to].push_back({ from, 0, (flow_type)G[from].size() - 1 }); } auto dfs = [&](auto&& f, flow_type v, flow_type t, flow_type fl)->int { if (v == t) return fl; used[v] = true; rep(i, G[v].size()) { edge_& e = G[v][i]; if (!used[e.to] && e.cap > 0) { flow_type d = f(f, e.to, t, min(fl, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; }; flow_type flow = 0; while (1) { used.assign(used.size(), false); flow_type f = dfs(dfs, s, t, INT_MAX); if (f == 0) return flow; flow += f; } } }; int main() { int h, w; cin >> h >> w; vector> grid(h, vector(w)); rep(y, h) { rep(x, w){ cin >> grid[y][x]; } } vector rows(h), cols(w); rep(i, h) cin >> rows[i]; rep(i, w) cin >> cols[i]; vector < vector>> graph(h*w + h*2 + w * 2 + 2); const int start = h * w + h * 2 + w * 2; const int goal = start + 1; const int rs = h * w; const int cs = h * w + 2 * h; rep(y, h) { rep(x, w) { int id = y * w + x; graph[start].emplace_back(grid[y][x], id); int xline = cs + x * 2; int yline = rs + y * 2; graph[id].emplace_back(1e16, xline); graph[id].emplace_back(1e16, yline); } } rep(y, h) { int yline = rs + y * 2; graph[yline].emplace_back(rows[y], yline + 1); graph[yline+1].emplace_back(1e16, goal); } rep(x, w) { int xline = cs + x * 2; graph[xline].emplace_back(cols[x], xline + 1); graph[xline + 1].emplace_back(1e16, goal); } ll sum = 0; rep(y, h) { sum += rows[y]; } rep(x, w) { sum += cols[x]; } MaxFlowCalculator f; auto a = f.max_flow(start, goal, graph); cout << sum - a << endl; return 0; }