from sys import setrecursionlimit, stdin from collections import defaultdict, deque, Counter from itertools import permutations, combinations, product from functools import lru_cache from bisect import bisect_left, bisect_right from heapq import heappush, heappop from copy import copy, deepcopy from decimal import Decimal from random import random, randrange # from pypyjit import set_param # set_param('max_unroll_recursion=-1') setrecursionlimit(1 << 20) readline = stdin.readline INF = 10 ** 18 MOD = 998244353 # MOD = 1000000007 ALP = 26 ''' Input ''' def I(): return int(readline()) def ST(): return readline()[:-1] def LI(): return list(map(int, readline().split())) def LII(): return list(map(lambda x: int(x) - 1, readline().split())) def LF(x, func): return [func() for _ in [0] * x] def SPI(): return map(int, readline().split()) def SPII(): return map(lambda x: int(x) - 1, readline().split()) def FIE(x): return [readline()[:-1] for _ in [0] * x] ''' Array ''' def cmin(dp, i, x): if x < dp[i]: dp[i] = x def cmax(dp, i, x): if x > dp[i]: dp[i] = x ''' Alphabet ''' def alp_a_to_i(s): return ord(s) - ord('a') def alp_A_to_i(s): return ord(s) - ord('A') def alp_i_to_a(i): return chr(ord('a') + i) def alp_i_to_A(i): return chr(ord('A') + i) ''' Other''' def nynx(y, x, H, W): return [(y + dy, x + dx) for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)] if 0 <= y + dy < H and 0 <= x + dx < W] def gen(x, *args): if len(args) == 1: return [x] * args[0] if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]] if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]] if len(args) == 4: return [[[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0]] ''' Output ''' def pprint(E): print() for e in E: print(e) def Yes(): print("Yes") def No(): print("No") def YES(): print("YES") def NO(): print("NO") def yn(x): print("Yes" if x else "No") def YN(x): print("YES" if x else "NO") ############################################################################################### H, W = SPI() A = LF(H - 2, LI) A = [[-1] * W] + A + [[-1] * W] dp = gen(INF, H, W) for i in range(H): if A[i][0] != -1: dp[i][0] = A[i][0] for j in range(1, W): for i in range(1, H - 1): if A[i][j] == -1: continue dp[i][j] = min(dp[i][j], dp[i + 1][j - 1], dp[i][j - 1], dp[i - 1][j - 1]) + A[i][j] # pprint(A) # pprint(dp) ans = INF for i in range(H): ans = min(ans, dp[i][W - 1]) if ans == INF: ans = -1 print(ans)