가중치 격자 최단 비용

첫 줄에 격자의 크기 n, m (1 이상 130 이하) 이 주어집니다. 이어서 n개의 줄에 각각 m개의 수가 주어집니다. 각 칸을 밟는 비용(1 이상 1000 이하)입니다.

왼쪽 위 (0,0) 에서 오른쪽 아래 (n-1,m-1) 까지 상하좌우로 이동할 때, 지나는 모든 칸(시작과 끝 포함)의 비용 합을 최소로 하면 얼마인지 출력하세요.

예시

입력

2 2
1 3
1 5

출력

7