from queue import PriorityQueue
import sys

class grid:
    def __init__(self):
        self.y = []
        self.attempts = 0
        self.solutions = []
        self.current_smallest_solution_level = None
        self.point_costs = {(0, 0): 0}
        self.next_point_queue = PriorityQueue()
        self.next_point_queue.put((0, (0, 0)))

    def addline(self, line):
        self.y.append([int(i) for i in line])
        self.maxy = len(self.y) - 1
        self.maxx = len(self.y[0]) - 1

        # print(self.maxx)
        # print(self.maxy)

    def findpath(self):
        while not self.next_point_queue.empty():
            level, poi = self.next_point_queue.get()
            self.attempts += 1
            if self.attempts % 100000 == 0:
                print('Attempt %d, solutions: %d, cost: %d' % (self.attempts, len(self.solutions), self.current_smallest_solution_level or -1))

            neighbors = self.get_neighbors(poi)

            for i in neighbors:
                next_level = level + int(self.y[i[0]][i[1]])
                if (self.current_smallest_solution_level is not None and
                    next_level > self.current_smallest_solution_level):
                    # We already found a solution that was overall less risky
                    # than the current path, so who cares.
                    continue
                if i == (self.maxy, self.maxx):
                    self.solutions.append(next_level)
                    if (self.current_smallest_solution_level is None or
                        next_level < self.current_smallest_solution_level):
                        self.current_smallest_solution_level = next_level
                    # print('Found solution: ', i, ', orig level ', level)
                    continue
                elif i in self.point_costs and self.point_costs[i] < next_level:
                    # We already visited the point on a cheaper path.
                    continue
                else:
                    # print('Path: %s, next: %s' % (repr(path), i))
                    self.point_costs[i] = next_level
                    self.next_point_queue.put((next_level, i))

    def get_neighbors(self, poi):
        nex = {}
        rv = []
        if poi[0] != self.maxy:
            nex.setdefault(self.y[poi[0] + 1][poi[1]], list()).append((poi[0] + 1, poi[1]))
        if poi[1] != self.maxx:
            nex.setdefault(self.y[poi[0]][poi[1] + 1], list()).append((poi[0], poi[1] + 1))
        if poi[0] != 0:
            nex.setdefault(self.y[poi[0] - 1][poi[1]], list()).append((poi[0] - 1, poi[1]))
        if poi[1] != 0:
            nex.setdefault(self.y[poi[0]][poi[1] - 1], list()).append((poi[0], poi[1] - 1))

        order = sorted(nex.keys())

        for j in order:
            rv += nex[j]

        return rv

gri = grid()

with open(sys.argv[1], 'r') as f:
    for i in f.readlines():
        gri.addline(i.strip())

gri.findpath()

print(min(gri.solutions))