새 분수

오늘 알파를 거닐던 로렐린은 곧 열리고 물로 채워질 새 분수를 발견했다. 이 분수에 물이 얼마나 담길지 궁금해졌다.

분수는 기둥들이 모인 형태다. 분수의 바닥은 $n \times m$ 직사각형 격자이며, $nm$개의 단위 정사각형으로 나뉜다. 행은 1부터 $n$까지, 열은 1부터 $m$까지 번호가 매겨진다. 각 칸에는 양의 정수 높이의 기둥이 하나씩 있고, $i$행 $j$열 칸의 기둥 높이는 $h_{i,j}$다.

분수가 열리면 위에서 물이 부어져 분수 안의 빈 공간을 모두 채운다. 형식적으로 말하면, 분수가 열리는 순간 각 기둥 위에 0 이상의 높이를 가진 물기둥이 생긴다. $i$행 $j$열 기둥 위의 물 높이를 $w_{i,j}$라고 하자. 다음 두 조건이 성립하면 물이 분수 밖으로 새지 않는다고 본다.

• $i \in \{1, n\}$ 또는 $j \in \{1, m\}$이면 $w_{i,j} = 0$이다. 즉, 가장자리 기둥에는 물이 없고 물은 분수 밖으로 빠진다.
• $|i_1 - i_2| + |j_1 - j_2| = 1$이면 $w_{i_1,j_1} = 0$이거나 $h_{i_1,j_1} + w_{i_1,j_1} \le h_{i_2,j_2} + w_{i_2,j_2}$이다. 즉, 물이 올라간 기둥의 전체 높이는 옆에 붙은 기둥 각각의 전체 높이를 넘지 않는다.

물의 총량은 모든 $w_{i,j}$의 합이다. 분수는 이 총량이 최대가 되도록 채워진다.

로렐린은 바닥 크기와 모든 기둥의 높이를 기억하지만, 담기는 물의 양은 계산하지 못했다. 이 값을 계산하는 프로그램을 작성해 달라.

첫 줄에는 바닥의 행 수와 열 수를 나타내는 정수 $n$과 $m$이 주어진다($3 \le n, m \le 900$). 다음 $n$개 줄에는 각각 $m$개의 정수가 주어진다. $i+1$번째 줄에는 $h_{i,1}, h_{i,2}, \dots, h_{i,m}$이 있으며, 이는 $i$행에 있는 기둥들의 높이다($1 \le h_{i,j} \le 10^9$).

분수에 담을 수 있는 물의 최대 총량을 정수 하나로 출력한다.

첫 번째 테스트에서는 $w_{2,2} = 2$, $w_{2,3} = 1$이고 나머지 모든 기둥의 $w_{i,j}$가 0일 때 최대 용량에 도달한다. 이 값들이 모든 조건을 만족하는 것은 쉽게 확인할 수 있으며, 물의 총량은 3이다.

두 번째 테스트에서는 두 기둥에만 물이 올라갈 수 있다. $w_{2,2} = 1$, $w_{2,3} = 1$이고 나머지 기둥의 $w_{i,j}$가 모두 0일 때 최대가 되며, 물의 총량은 2이다.