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

아래와 같은 5×5 행렬이 있습니다. 좌측 상단에서 출발해서 상하좌우로 움직이면서 우측 하단까지 가는 경로의 합을 구해 보면, 빨갛게 표시된 경로가 2297로서 가장 작습니다.

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 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 좌측 상단에서 출발하여 우측 하단까지 갈 때, 경로 합의 최솟값은 얼마입니까?