# The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any
# cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.
#
# Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a
# 80 by 80 matrix, from the left column to the right column.


from copy import deepcopy

with open("p082_matrix.txt") as f:
    lines = f.readlines()

matrix = [[int(x) for x in line.strip().split(",")] for line in lines]

initial_matrix = deepcopy(matrix)

n = len(matrix)

for j in range(1, n):
    matrix[0][j] += matrix[0][j - 1]
    for i in range(1, n - 1):
        matrix[i][j] += min(matrix[i - 1][j], matrix[i][j - 1])
    matrix[n - 1][j] += min(matrix[n - 2][j], matrix[n - 1][j - 1])
    for i in reversed(range(0, n - 1)):
        matrix[i][j] = min(matrix[i][j], matrix[i + 1][j] + initial_matrix[i][j])

print(min(matrix[j][-1] for j in range(len(matrix))))