위 행렬은 3x4의 2차원 비용 행렬을 나타냅니다. 각 칸의 수는 그 칸을 통과하는데 드는 비용을 나타냅니다. 위와 같은 행렬의 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 가는 데 드는 총 비용을 최소로 하는 방법은 다음과 같습니다.

이때 드는 최소 비용의 합은 12입니다.

비용 행렬이 주어졌을 때 행렬의 가장 좌상단 셀에서 가장 우하단 셀로 이동하는데 드는 최소 비용을 구하는 코드를 작성하시오. 단, 오른쪽과 아래쪽으로 한 셀씩만 이동할 수 있습니다.

입력

첫째 줄엔 수 n과 m(m은 행렬의 가로, n은 행렬의 세로, 0 < n, m < 501)을 공백을 사이로 입력

다음 n개의 줄엔 각각 m개의 수를 공백을 사이로 입력

출력

행렬의 가장 좌상단 셀에서 가장 우하단 셀로 이동하는 데 드는 최소 비용을 출력

제한시간: 1초

메모리제한: 1MB