def test(input, solution):
    # print(f"Running input {input}")
    result = process(input)
    print(f"Solution was {result}")
    assert result == solution

def run():
    file = open("input.txt", "r")
    return process(file.read()[:-1])

def neighbors(node, height, width):
    (down, right) = node
    current_neighbors = [("D", (down+1, right)), ("U", (down-1, right)), ("R", (down, right+1)), ("L", (down, right-1))]
    if down == 0:
        current_neighbors.remove(("U", (down-1, right)))
    if down == height:
        current_neighbors.remove(("D", (down+1, right)))
    if right == 0:
        current_neighbors.remove(("L", (down, right-1)))
    if right == width:
        current_neighbors.remove(("R", (down, right+1)))
    return current_neighbors

def dijkstra(input):
    down = len(input.split("\n")) - 1
    right = len(input.split("\n")[0]) - 1
    unvisited_nodes = {}
    visited_nodes = {}
    current_node = (0, 0, 0, 0) # x, y, direction of last move x, direction of last move y
    unvisited_nodes[0, 0, 0, 0] = 0
    # This is genius. Shamelessly stolen. Easy bounds checking by making a dict of indices -> scores
    board = { (i,j): int(cell) for i,row in enumerate(input.split('\n')) for j,cell in enumerate(row) }
    while unvisited_nodes:
        current_node = sorted(unvisited_nodes.items(), key=lambda item: item[1])[0][0]
        (x,y,dx_last,dy_last) = current_node
        current_score = unvisited_nodes[current_node]
        del unvisited_nodes[current_node]
        if current_node[0] == down and current_node[1] == right: return current_score
        if current_node in visited_nodes: continue
        visited_nodes[current_node] = current_score
        possible_directions = {(1,0), (-1,0), (0,1), (0,-1)} - {(dx_last,dy_last), (-dx_last,-dy_last)}
        for (dx, dy) in possible_directions:
            new_x, new_y, new_score = x, y, current_score
            for i in range(1,11):
                new_x = new_x + dx
                new_y = new_y + dy
                if (new_x, new_y) in board:
                    new_score += board[new_x, new_y]
                    if i >= 4:
                        if (new_x, new_y, dx, dy) not in unvisited_nodes:
                            unvisited_nodes[(new_x, new_y, dx, dy)] = new_score
                        elif new_score < unvisited_nodes[(new_x, new_y, dx, dy)]:
                            unvisited_nodes[(new_x, new_y, dx, dy)] = new_score
    return int("inf")


def process(input):
    sol = dijkstra(input)
    return sol