Bob Batch 컴파일 명령

Bob는 유명한 건축업자입니다. 그는 땅을 샀고 집을 짓고 싶습니다. 불운하게도, 문제는 그 섬의 지형으로, 고도의 변동이 심합니다.

그 땅은 좌우로 $N$미터, 위아래로 $M$미터 길이의 직사각형처럼 생겼습니다. 그 땅은 $N \times M$개의 정사각형들로 분할될 수 있습니다. (그림을 보세요) Bob의 집은, 변이 땅의 가장자리와 평행하고, 꼭짓점들이 정사각형들의 꼭짓점들과 일치하는 직사각형 모양일 것입니다. 승현이의 집이 지어지는 부분은, 붕괴를 방지하기 위해 높이가 모두 같아야 합니다.

정사각형들로 분할된 땅. 집을 지을 수 있는 두 가지 방법이 빨강색과 파랑색으로 색칠되어 있습니다.

입력 형식

첫 번째 줄에 두 개의 정수 $N$과 $M$ ($1 \le N, M \le 1 000$)이 주어집니다.

다음 $N$개의 줄에는 각각 $M$개의 정수들 $ai,j$ ( $1 \le ai,j \le 10^{9}$)이 공백을 사이로 두고 주어집니다. 이 정수들은 땅의 각 정사각형의 해발 고도를 나타냅니다.

주의 입력량이 매우 크므로 빠른 입출력 방식을 사용하세요

출력 형식

첫 번째 줄에 문제에서 요구하는 답을 출력합니다.

채점 방식

20%의 점수에 해당하는 테스트 케이스들은 $N, M \le 50$을 만족합니다.

60%의 점수에 해당하는 테스트 케이스들은 $N, M \le 500$을 만족합니다.

예제 1

입력

5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1

출력

27

예제 2

입력

4 3
1 1 1
1 1 1
2 2 2
2 2 2

출력

36

첫 번째 예제의 설명: 집을 지을 수 있는 가능한 방법들에는 (0, 0)-(1, 1), (0, 0)-(0, 2), (2, 0)-(2, 2), (1, 2)-(2, 2) 등이 있습니다. 괄호 내의 첫 번째 수는 열 번호를, 두 번째 수는 행 번호를 나타내며, 번호는 0에서부터 시작하여 차례대로 붙습니다. (a, b)-(c, d)는 왼쪽 위 꼭짓점이 (a, b)이고 오른쪽 아래 꼭짓점이 (c, d)인 직사각형을 나타냅니다.