(참고: 이 문제는 81번 문제의 좀 더 어려운 버전입니다)

아래와 같은 5×5 행렬이 있습니다. 맨 왼쪽 열의 아무 곳에서나 출발하여 위/아래/오른쪽으로만 움직이면서 맨 오른쪽 열까지 갈 때, 빨갛게 표시된 경로의 합이 994로 가장 작습니다.

131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

31KB짜리 파일 matrix.txt에는 80×80 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 맨 왼쪽 열에서 출발하여 맨 오른쪽 열까지 갈 때, 경로 합의 최솟값은 얼마입니까?