만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수영장

면접 대비

시간 제한1초메모리 제한128 MB

요약
m×n 격자에 탑의 높이가 주어질 때, 바깥에서 물을 채웠을 때 탑 사이에 고이는 물의 총 부피를 구한다.
난이도

보통10점 중 6점

유형
힙, BFS, 그래프, 행렬
정답자
아직 제출이 없습니다

문제

옛날에는 수영장을 다음과 같이 만들었습니다. 먼저 가로 mm미터, 세로 nn미터 크기의 직사각형 영역을 정합니다. 이 영역을 한 변의 길이가 1미터인 정사각형 칸으로 나누면 m×nm \times n개의 칸이 생깁니다. 그런 다음 각 칸에는 한 변의 길이가 1인 완벽하게 재단된 화강암 정육면체 하나, 또는 이런 정육면체를 쌓아 올린 탑을 놓습니다.

정육면체는 매우 정밀하게 만들어져서, 두 정육면체의 모서리가 서로 맞닿기만 해도 그 사이가 완전히 밀봉되어 물이 새지 않습니다.

물을 흘려보내면 이렇게 쌓은 '정육면체 더미'는 제한된 양의 물만 담을 수 있습니다.

이 수영장에 담을 수 있는 물의 최대 부피(세제곱미터)를 구하는 프로그램을 작성하세요.

입력

첫째 줄에 직사각형 영역의 두 변의 길이인 양의 정수 mm과 nn이 주어집니다 (0<m,n≤1000 < m, n \le 100).

다음 mm개의 줄에는 각각 nn개의 자연수가 주어집니다.

i+1i+1번째 줄의 jj번째 수는 ii번째 행, jj번째 열에 놓인 정육면체 탑의 높이(즉, 그 칸에 쌓인 정육면체의 개수)를 나타냅니다. 모든 칸에는 정육면체가 적어도 하나 있으며, 어떤 칸에서도 탑의 높이는 10000을 넘지 않습니다.

출력

표준 출력의 유일한 줄에, 주어진 수영장에 담을 수 있는 물의 최대 부피(세제곱미터)를 나타내는 정수 하나를 출력합니다.

힌트

아래 그림은 빈 수영장과 물이 가득 찬 수영장을 위에서 내려다본 모습입니다.

예제1

  1. 예제 1

    입력
    3 6
    3 3 4 5 4 2
    3 1 3 2 1 3
    6 3 1 4 3 1
    
    예상 출력
    5