Bob Batch 컴파일 명령

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

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

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

입력 형식

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

다음 N개의 줄에는 각각 M개의 정수들 a_i,j ( 1 ≤ a_i,j ≤ 10⁹)이 공백을 사이로 두고 주어집니다. 이 정수들은 땅의 각 정사각형의 해발 고도를 나타냅니다.

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

출력 형식

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

채점 방식

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

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

첫 번째 예제의 설명: 집을 지을 수 있는 가능한 방법들에는 (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)인 직사각형을 나타냅니다.