#include #include // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_PROJECT_SELECTION_HPP #define KOTONE_PROJECT_SELECTION_HPP 1 #include namespace kotone { // A minimal wrapper for solving project selection problems using flow network algorithm. template struct project_selection { atcoder::mf_graph graph; int source, sink; // Constructs a flow network for the specified number of projects. project_selection(int num_projects) : graph(num_projects + 2), source(num_projects), sink(num_projects + 1) {} // Adds the specified cost if project `i` is assigned `b`. // Requires `0 <= i < num_projects`. // Requires `cost >= 0`. void add_single(int i, bool b, Cap cost) { if (b) graph.add_edge(i, sink, cost); else graph.add_edge(source, i, cost); } // Adds the specified cost if project `i` is assigned `true` and project `j` is assigned `false`. // Requires `0 <= i, j < num_projects`. // Requires `cost >= 0`. void add_pair(int i, int j, Cap cost) { graph.add_edge(i, j, cost); } // Finds an optimal assignment and returns the minimum cost. // This function should be called once after adding constraints to the flow network. Cap eval_cost() { return graph.flow(source, sink); } // Returns a vector of `bool` indicating the assignment of each project. // This function should be called after `eval_cost`. std::vector assignment() { std::vector result = graph.min_cut(source); result.pop_back(); result.pop_back(); return result; } }; } // namespace kotone #endif // KOTONE_PROJECT_SELECTION_HPP int main() { int H, W; std::cin >> H >> W; kotone::project_selection graph(H * W + H + W); int64_t revenue = 0; for (int i = 0; i < H * W; i++) { int64_t g; std::cin >> g; graph.add_single(i, true, g); } for (int i = 0; i < H; i++) { int64_t r; std::cin >> r; revenue += r; graph.add_single(i + H * W, false, r); for (int j = 0; j < W; j++) graph.add_pair(i + H * W, i * W + j, 1LL << 60); } for (int j = 0; j < W; j++) { int64_t c; std::cin >> c; revenue += c; graph.add_single(j + H * W + H, false, c); for (int i = 0; i < H; i++) graph.add_pair(j + H * W + H, i * W + j, 1LL << 60); } std::cout << revenue - graph.eval_cost() << std::endl; }