import sys from collections import deque class Edge: def __init__(self, to, rev, capacity): self.to = to self.rev = rev self.capacity = capacity class MaxFlow: def __init__(self, n): self.size = n self.graph = [[] for _ in range(n)] def add_edge(self, fr, to, cap): forward = Edge(to, len(self.graph[to]), cap) backward = Edge(fr, len(self.graph[fr]), 0) self.graph[fr].append(forward) self.graph[to].append(backward) def bfs_level(self, s, t, level): q = deque() level[:] = [-1] * self.size level[s] = 0 q.append(s) while q: v = q.popleft() for edge in self.graph[v]: if edge.capacity > 0 and level[edge.to] == -1: level[edge.to] = level[v] + 1 q.append(edge.to) if edge.to == t: return return def dfs_flow(self, v, t, upTo, iter_, level): if v == t: return upTo for i in range(iter_[v], len(self.graph[v])): edge = self.graph[v][i] if edge.capacity > 0 and level[v] < level[edge.to]: d = self.dfs_flow(edge.to, t, min(upTo, edge.capacity), iter_, level) if d > 0: edge.capacity -= d self.graph[edge.to][edge.rev].capacity += d return d iter_[v] += 1 return 0 def max_flow(self, s, t): flow = 0 level = [-1] * self.size while True: self.bfs_level(s, t, level) if level[t] == -1: return flow iter_ = [0] * self.size while True: f = self.dfs_flow(s, t, float('inf'), iter_, level) if f == 0: break flow += f level = [-1] * self.size return flow def main(): H, W = map(int, sys.stdin.readline().split()) G = [] for _ in range(H): G.append(list(map(int, sys.stdin.readline().split()))) R = list(map(int, sys.stdin.readline().split())) C = list(map(int, sys.stdin.readline().split())) # Compute A and B A = [] for i in range(H): total = sum(G[i]) A.append(R[i] - total) B = [] for j in range(W): total = sum(G[i][j] for i in range(H)) B.append(C[j] - total) # Compute the sum of positive terms for maximum possible total_positive = 0 # Create nodes: rows (0..H-1), cols (H..H+W-1), edges (H+W..H+W+H*W-1) edge_node_start = H + W total_nodes = edge_node_start + H * W S = total_nodes T = S + 1 mf = MaxFlow(T + 1) INF = 1 << 60 # Add row nodes for i in range(H): a = A[i] if a > 0: mf.add_edge(S, i, a) total_positive += a else: mf.add_edge(i, T, -a) # Add column nodes for j in range(W): b = B[j] if b > 0: mf.add_edge(S, H + j, b) total_positive += b else: mf.add_edge(H + j, T, -b) # Add edge nodes for each i,j for i in range(H): for j in range(W): g = G[i][j] edge_node = edge_node_start + i * W + j if g > 0: mf.add_edge(S, edge_node, g) total_positive += g else: mf.add_edge(edge_node, T, -g) # Add edges from edge_node to row i and column j mf.add_edge(edge_node, i, INF) mf.add_edge(edge_node, H + j, INF) max_flow_val = mf.max_flow(S, T) result = total_positive - max_flow_val print(result) if __name__ == "__main__": main()