#ZONe2021E Sneaking
#入力受取 R, Cは慣れないのでH, Wに変更
R, C = map(int, input().split())
H, W = R, C
A = [tuple(map(int, input().split())) for _ in range(H)]
B = [tuple(map(int, input().split())) for _ in range(H - 1)]
#頂点を倍加し、辺を張り直す
#(h, w, f): 現在値が(h, w)で、f = 1なら高速道路に移動した状態
convert = lambda h, w, f: (h * W + w) << 1 | f
G = [[] for _ in range(H * W * 2)]
#1. 左右の移動: コストA
for h in range(H):
for w in range(W - 1):
G[ convert(h, w, 0) ].append( (convert(h, w + 1, 0), A[h][w]) )
G[ convert(h, w + 1, 0) ].append( (convert(h, w, 0), A[h][w]) )
#2. 上下の移動: コストB
for h in range(H - 1):
for w in range(W):
G[ convert(h, w, 0) ].append( (convert(h + 1, w, 0), B[h][w]) )
#3. 倍加した頂点間の移動: 倍加先に入るとコスト1
for h in range(H):
for w in range(W):
G[ convert(h, w, 0) ].append( (convert(h, w, 1), 1) )
G[ convert(h, w, 1) ].append( (convert(h, w, 0), 0) )
#4. 倍加先の頂点の移動: 1マス降りるとコスト1
for h in range(H - 1):
for w in range(W):
G[ convert(h + 1, w, 1) ].append( (convert(h, w, 1), 1) )
#convert(0, 0, 0) から convert(H - 1, W - 1, 0) の最短路を求める問題に帰着できた
#ダイクストラだとおそらくTLEするのでDial algo.を用いる
#1. ダイクストラ法(SegTree)
def solve_SegTree():
#dijkstra用SegTree 距離のchmin操作に対応
class dijkstra_SegTree: #ノードにvalueを直接代入する
def __init__(self, N, inf):
self._N, self._logN, self._size = N, N.bit_length(), 1 << N.bit_length()
self._dist, self._node = [inf] * N, [inf] * (self._size << 1)
def build(self, A): #distをarray Aで初期化 O(N)
assert len(A) == self._N
for i, v in enumerate(A): self._dist[i] = self._node[i | self._size] = v
for i in range(self._size - 1, 0, -1):
self._node[i] = min(self._node[i << 1], self._node[i << 1 | 1])
def chmin(self, i, v): #dist[i] ← min(dist[i], v) O(logN)
if v < self._dist[i]:
self._dist[i] = self._node[now := i | self._size] = v
for _ in range(self._logN):
if v < self._node[now := now >> 1]: self._node[now] = v
else: return
def get(self): #【まだpopしていない】距離最小の頂点を取り出す なければ-1 Θ(logN)
if (v := self._node[now := 1]) == self._node[0]: return -1
for _ in range(self._logN): now = e if self._node[e := now << 1] == v else e | 1
m = self._node[i := now] = self._node[0]
for _ in range(self._logN):
if self._node[now ^ 1] < m: m = self._node[now ^ 1]
self._node[now := now >> 1] = m
return i ^ self._size
def dist(self, i): return self._dist[i]
ST = dijkstra_SegTree(H * W * 2, H * W * 10 ** 3)
ST.chmin(convert(0, 0, 0), 0) #初期化
while True:
i = ST.get()
if i == -1: break
for nxt, Ci in G[i]:
ST.chmin(nxt, ST.dist(i) + Ci)
return ST.dist( convert(H - 1, W - 1, 0) )
#2. ダイクストラ法(heapq)
def solve_heapq():
import heapq
DP = [H * W * 10 ** 3] * H * W * 2
DP[0] = 0
Q = [(0, 0)]
while Q:
dist, now = heapq.heappop(Q)
if DP[now] < dist: continue
DP[now] = dist
for nxt, Ci in G[now]:
if DP[nxt] > DP[now] + Ci:
DP[nxt] = DP[now] + Ci
heapq.heappush(Q, (DP[nxt], nxt))
return DP[ convert(H - 1, W - 1, 0) ]
#2+. heapqを高速化 距離の最大値は2^31以下なのでtupleを回避できる
def solve_heapq_2():
import heapq
DP = [H * W * 10 ** 3] * H * W * 2
DP[0] = 0
mask = (1 << 31) - 1
Q = [0 << 31 | 0]
while Q:
x = heapq.heappop(Q)
dist, now = x >> 31, x & mask
if DP[now] < dist: continue
DP[now] = dist
for nxt, Ci in G[now]:
if DP[nxt] > DP[now] + Ci:
DP[nxt] = DP[now] + Ci
heapq.heappush(Q, DP[nxt] << 31 | nxt)
return DP[ convert(H - 1, W - 1, 0) ]
#3. Dial algorithm
def solve_dial():
#DP[i]: 頂点iの最短距離
DP = [H * W * 10 ** 3] * H * W * 2
DP[0] = 0
Q = [[] for _ in range(1 << 10)] #Dial algoのスタック
Q[0].append(0)
mask = (1 << 10) - 1 #除算用 ダイアル長が2冪ならand演算でよい
for _ in range(- ( (- H * W * 10 ** 3) >> 10 )): #最長距離を予測する
for d in range(1 << 10):
while Q[d]:
i = Q[d].pop()
if DP[i] & mask != d: continue
for nxt, Ci in G[i]:
if DP[nxt] > DP[i] + Ci:
DP[nxt] = DP[i] + Ci
Q[ DP[nxt] & mask ].append(nxt)
return DP[ convert(H - 1, W - 1, 0) ]
print(solve_dial())