호수 만들기

Farmer John은 소들의 도움을 받아 호수를 파려고 합니다. 그는 목초지를 한 변이 6피트인 정사각형 칸들로 이루어진 $R$ ($3 \le R \le 100$)행 $C$ ($3 \le C \le 100$)열 격자로 나타내고, 각 칸의 평균 고도를 인치 단위로 기록했습니다 ($10 \le \text{elev} \le 5000$).

또한 그는 소들에게 "밟아 파기"를 훈련시켰습니다. 하나의 명령은 왼쪽 위 칸이 $R_s$행 ($1 \le R_s \le R-2$), $C_s$열 ($1 \le C_s \le C-2$)에 오는 $3 \times 3$ 블록을 정확히 덮는 소 떼를 보냅니다. 소 떼는 땅을 $D_s$ ($1 \le D_s \le 40$)인치만큼 밟아 내리누릅니다. 그런데 소들은 꼼꼼해서, 더 낮은 칸에 있는 소들은 내려오는 땅의 높이가 자기 높이에 닿을 때까지 밟기를 시작하지 않습니다. 그 결과 충분히 높은 칸만 내려가고, 블록 전체는 하나의 바닥 높이 — 블록 안 최대 고도에서 $D_s$를 뺀 값 — 로 평탄해집니다.

정확히 말하면, 블록의 아홉 칸 중 최대 고도를 $m$이라 하고 $f = m - D_s$라 합시다. 명령이 끝나면 블록 안에서 고도가 $f$보다 큰 칸은 모두 정확히 $f$가 되고, 이미 $f$ 이하인 칸은 변하지 않습니다. (고도는 음수가 될 수도 있습니다.)

초기 고도, 순서대로 적용되는 $N$ ($1 \le N \le 20000$)개의 밟아 파기 명령, 그리고 최종 수위 $E$ ($0 \le E \le 5000$)가 주어집니다. 모든 명령을 적용한 뒤, 각 칸은 고도가 $E$보다 낮을 때 $E$에서 그 칸의 고도를 뺀 깊이만큼 물을 담습니다 (고도가 $E$ 이상인 칸은 물을 담지 않습니다). 목초지의 가장자리는 방벽 역할을 하므로 물은 경계 밖으로 넘치지 않으며, 깊이는 칸별로 계산합니다.

각 칸은 $6\text{ft} \times 6\text{ft} = 72\text{in} \times 72\text{in}$이므로, 한 칸의 물 부피는 그 칸의 깊이(인치)에 $72 \times 72$ 제곱인치를 곱한 값입니다. 호수가 담는 물의 총 부피를 세제곱인치 단위로 구하세요. 정답은 $2{,}000{,}000{,}000$을 넘지 않음이 보장됩니다.

풀이 예시. 다음과 같은 초기 고도를 가진 $4 \times 6$ 목초지를 생각해 봅시다:

       c1 c2 c3 c4 c5 c6
  r1:  28 25 20 32 34 36
  r2:  27 25 20 20 30 34
  r3:  24 20 20 20 20 30
  r4:  20 20 14 14 20 20

명령 1 4 4(왼쪽 위 칸이 1행 4열, 깊이 4)을 적용합니다. 블록은 13행, 46열을 덮고 최대 고도는 36이므로 바닥은 $36 - 4 = 32$이며, 32보다 높은 세 칸만 내려갑니다:

       c1 c2 c3 c4 c5 c6
  r1:  28 25 20 32 32 32
  r2:  27 25 20 20 30 32
  r3:  24 20 20 20 20 30
  r4:  20 20 14 14 20 20

다음으로 1 1 10을 적용합니다. 블록은 13행, 13열을 덮고 최대 고도는 28이므로 바닥은 $28 - 10 = 18$이 되어 블록의 모든 칸이 18로 내려갑니다:

       c1 c2 c3 c4 c5 c6
  r1:  18 18 18 32 32 32
  r2:  18 18 18 20 30 32
  r3:  18 18 18 20 20 30
  r4:  20 20 14 14 20 20

최종 수위가 $E = 22$일 때 각 칸의 깊이는 다음과 같습니다 (점은 물을 담지 않는 칸입니다):

       c1 c2 c3 c4 c5 c6
  r1:   4  4  4  .  .  .
  r2:   4  4  4  2  .  .
  r3:   4  4  4  2  2  .
  r4:   2  2  8  8  2  2

총 깊이는 66인치이므로 부피는 $66 \times 72 \times 72 = 342144$ 세제곱인치입니다.

• 첫째 줄: 공백으로 구분된 네 정수 $R$, $C$, $E$, $N$.
• 둘째 줄부터 $R+1$째 줄까지: $i+1$째 줄은 $i$행의 고도를 나타내는 $C$개의 정수를 공백으로 구분하여 담습니다.
• $R+2$째 줄부터 $R+N+1$째 줄까지: $i+R+1$째 줄은 $i$번째 밟아 파기 명령을 나타내는 세 정수 $R_s$, $C_s$, $D_s$를 공백으로 구분하여 담습니다.

• 정수 하나: 호수가 담는 물의 총 부피(세제곱인치).