import sys # sys.setrecursionlimit(1000005) # sys.set_int_max_str_digits(200005) int1 = lambda x: int(x)-1 pDB = lambda *x: print(*x, end="\n", file=sys.stderr) p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr) def II(): return int(sys.stdin.readline()) def LI(): return list(map(int, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def LI1(): return list(map(int1, sys.stdin.readline().split())) def LLI1(rows_number): return [LI1() for _ in range(rows_number)] def SI(): return sys.stdin.readline().rstrip() dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] # dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)] # inf = -1-(-1 << 31) inf = -1-(-1 << 63) # md = 10**9+7 md = 998244353 from typing import NamedTuple, Optional, List, cast class MFGraph: class Edge(NamedTuple): src: int dst: int cap: int flow: int class _Edge: def __init__(self, dst: int, cap: int) -> None: self.dst = dst self.cap = cap self.rev: Optional[MFGraph._Edge] = None def __init__(self, n: int) -> None: self._n = n+2 self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n+2)] self._edges: List[MFGraph._Edge] = [] self._lower_sum = 0 def add_edge(self, src: int, dst: int, cap: int) -> int: assert 0 <= src < self._n assert 0 <= dst < self._n assert 0 <= cap m = len(self._edges) e = MFGraph._Edge(dst, cap) re = MFGraph._Edge(src, 0) e.rev = re re.rev = e self._g[src].append(e) self._g[dst].append(re) self._edges.append(e) return m # cap's range [l,r] def add_edge_lr(self, src: int, dst: int, l: int, r: int) -> int: assert 0 <= src < self._n assert 0 <= dst < self._n assert 0 <= l <= r if r-l: self.add_edge(src, dst, r-l) self.add_edge(src, self._n-1, l) self.add_edge(self._n-2, dst, l) self._lower_sum += l def add_undir_edge(self, src: int, dst: int, cap: int) -> int: assert 0 <= src < self._n assert 0 <= dst < self._n assert 0 <= cap m = len(self._edges) e = MFGraph._Edge(dst, cap) re = MFGraph._Edge(src, cap) e.rev = re re.rev = e self._g[src].append(e) self._g[dst].append(re) self._edges.append(e) return m def get_edge(self, i: int) -> Edge: assert 0 <= i < len(self._edges) e = self._edges[i] re = cast(MFGraph._Edge, e.rev) return MFGraph.Edge( re.dst, e.dst, e.cap+re.cap, re.cap ) def edges(self) -> List[Edge]: return [self.get_edge(i) for i in range(len(self._edges))] def change_edge(self, i: int, new_cap: int, new_flow: int) -> None: assert 0 <= i < len(self._edges) assert 0 <= new_flow <= new_cap e = self._edges[i] e.cap = new_cap-new_flow assert e.rev is not None e.rev.cap = new_flow def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int: assert 0 <= s < self._n assert 0 <= t < self._n assert s != t if flow_limit is None: flow_limit = cast(int, sum(e.cap for e in self._g[s])) current_edge = [0]*self._n level = [0]*self._n def fill(arr: List[int], value: int) -> None: for i in range(len(arr)): arr[i] = value def bfs() -> bool: fill(level, self._n) queue = [] q_front = 0 queue.append(s) level[s] = 0 while q_front < len(queue): v = queue[q_front] q_front += 1 next_level = level[v]+1 for e in self._g[v]: if e.cap == 0 or level[e.dst] <= next_level: continue level[e.dst] = next_level if e.dst == t: return True queue.append(e.dst) return False def dfs(lim: int) -> int: stack = [] edge_stack: List[MFGraph._Edge] = [] stack.append(t) while stack: v = stack[-1] if v == s: flow = min(lim, min(e.cap for e in edge_stack)) for e in edge_stack: e.cap -= flow assert e.rev is not None e.rev.cap += flow return flow next_level = level[v]-1 while current_edge[v] < len(self._g[v]): e = self._g[v][current_edge[v]] re = cast(MFGraph._Edge, e.rev) if level[e.dst] != next_level or re.cap == 0: current_edge[v] += 1 continue stack.append(e.dst) edge_stack.append(re) break else: stack.pop() if edge_stack: edge_stack.pop() level[v] = self._n return 0 flow = 0 while flow < flow_limit: if not bfs(): break fill(current_edge, 0) while flow < flow_limit: f = dfs(flow_limit-flow) flow += f if f == 0: break return flow def flow_lr(self, s: int, t: int, flow_limit: Optional[int] = None) -> int: assert 0 <= s < self._n assert 0 <= t < self._n assert s != t if flow_limit: flow_limit -= self._lower_sum if flow_limit < 0: return -1 f = self.flow(self._n-2, self._n-1)*2 f += self.flow(self._n-2, t) f += self.flow(s, self._n-1) if f < self._lower_sum*2: return -1 f = self.flow(s, t, flow_limit) return f+self._lower_sum def min_cut(self, s: int) -> List[bool]: visited = [False]*self._n stack = [s] visited[s] = True while stack: v = stack.pop() for e in self._g[v]: if e.cap > 0 and not visited[e.dst]: visited[e.dst] = True stack.append(e.dst) return visited from collections import deque class Dinic: def __init__(self, n, s, t): self.n, self.s, self.t = n, s, t self.to = [[] for _ in range(n)] self.max_flow = -1 def add_edge(self, u, v, cap): u_index_in_to_v = len(self.to[v]) v_index_in_to_u = len(self.to[u]) self.to[u].append([v, cap, u_index_in_to_v]) self.to[v].append([u, 0, v_index_in_to_u]) # 無向辺の追加 def add_undir_edge(self, u, v, cap): u_index_in_to_v = len(self.to[v]) v_index_in_to_u = len(self.to[u]) self.to[u].append([v, cap, u_index_in_to_v]) self.to[v].append([u, cap, v_index_in_to_u]) def __set_level(self): s = self.s level = [-1] * self.n level[s] = 0 q = deque() q.append([s, 0]) while q: u, u_level = q.popleft() for v, cap, _ in self.to[u]: if cap == 0: continue if level[v] != -1: continue level[v] = u_level + 1 if v == self.t: self.level = level return True q.append([v, u_level + 1]) return False def __dfs(self, u=-1, flow_to_me=10 ** 16): if u == -1: u = self.s if u == self.t: return flow_to_me flow_from_me = 0 u_level = self.level[u] for utov_i, (v, cap, vtou_i) in enumerate(self.to[u]): if self.level[v] != u_level + 1: continue if cap == 0: continue flow_to_v = self.__dfs(v, min(cap, flow_to_me - flow_from_me)) if not flow_to_v: continue flow_from_me += flow_to_v self.to[u][utov_i][1] -= flow_to_v self.to[v][vtou_i][1] += flow_to_v return flow_from_me def __calculation(self): res = 0 while self.__set_level(): res += self.__dfs() return res # これが出力用 def get_max_flow(self): if self.max_flow == -1: self.max_flow = self.__calculation() return self.max_flow h,w=LI() gg=LLI(h) rr=LI() cc=LI() s=h+w t=s+1 mf=Dinic(h+w+2,s,t) ans=0 for u,r in enumerate(rr): mf.add_edge(s,u,r) mf.add_edge(u,t,sum(gg[u])) ans+=r for u,c in enumerate(cc,h): mf.add_edge(s,u,c) ans+=c for v in range(h): mf.add_edge(u,v,gg[v][u-h]) ans-=mf.get_max_flow() print(ans)