from heapq import heappush, heappop

input = open("input", 'r')

d = [[int(num) for num in line.rstrip()] for line in input]
hgt = len(d)
wdt = len(d[0])

def dkstr(mn=1,mx=3):
    s = set()
    q = [(0,0,0,0,0)]
    while q:
        h,x,y,dx,dy = heappop(q)
        if (x,y,dx,dy) in s:
            continue
        if (x,y) == (wdt-1,hgt-1):
            return h
        s.add((x,y,dx,dy))
        for ndx, ndy in [(0,1),(0,-1),(1,0),(-1,0)]:
            if (ndx, ndy) == (dx,dy) or (ndx,ndy) == (-dx,-dy):
                continue
            nx, ny, nh = x, y, h
            for i in range(1,mx+1):
                nx += ndx
                ny += ndy
                if (nx < 0 or nx >= wdt) or (ny < 0 or ny >= hgt):
                    break
                nh += d[ny][nx]
                if i >= mn:
                    heappush(q, (nh,nx,ny,ndx,ndy))
    return -1

print(dkstr())
print(dkstr(4,10))