Lake Making

Farmer John wants his cows to help him dig a lake. He has mapped the pasture as an $R$ ($3 \le R \le 100$) by $C$ ($3 \le C \le 100$) grid of six-foot-by-six-foot squares and recorded the average elevation of each square in inches ($10 \le \text{elev} \le 5000$).

He has also trained the cows in "stomp digging". One instruction sends a herd that exactly covers a $3 \times 3$ block of squares whose upper-left square is at row $R_s$ ($1 \le R_s \le R-2$) and column $C_s$ ($1 \le C_s \le C-2$). The herd stomps the ground down by $D_s$ ($1 \le D_s \le 40$) inches, but the cows are meticulous: those standing on lower squares do not start stomping until the descending ground reaches their level. As a result, only the squares that are high enough are pushed down, and the whole block is flattened to a single floor level equal to the block's maximum elevation minus $D_s$.

Formally, let $m$ be the highest elevation among the nine squares of the block and let $f = m - D_s$. After the instruction, every square in the block whose elevation is greater than $f$ becomes exactly $f$, while squares already at or below $f$ are unchanged. (An elevation may become negative.)

You are given the initial elevations, an ordered list of $N$ ($1 \le N \le 20000$) stomp-digging instructions applied in order, and a final water level $E$ ($0 \le E \le 5000$). After all instructions are applied, each square holds water to a depth of $E$ minus its elevation whenever its elevation is below $E$ (a square at or above $E$ holds no water). The edges of the pasture act as barriers, so water never spills over the border and the depth is computed square by square.

Each square is $6\text{ ft} \times 6\text{ ft} = 72\text{ in} \times 72\text{ in}$, so its water volume equals its depth in inches times $72 \times 72$ square inches. Report the total volume of water the lake holds, in cubic inches. The answer is guaranteed not to exceed $2{,}000{,}000{,}000$.

Worked example. Consider a $4 \times 6$ pasture with these initial elevations:

       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

Apply the instruction 1 4 4 (upper-left square at row 1, column 4, depth 4). The block covers rows 1-3 and columns 4-6; its highest elevation is 36, so the floor is $36 - 4 = 32$ and only the three squares above 32 are lowered:

       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

Next apply 1 1 10. The block covers rows 1-3 and columns 1-3; its highest elevation is 28, so the floor is $28 - 10 = 18$ and every square in the block drops to 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

With a final water level of $E = 22$, the depths are as follows (a dot means the square holds no water):

       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

The total depth is 66 inches, so the volume is $66 \times 72 \times 72 = 342144$ cubic inches.

• Line 1: four space-separated integers $R$, $C$, $E$, and $N$.
• Lines 2 to $R+1$: line $i+1$ contains $C$ space-separated integers giving the elevations of row $i$.
• Lines $R+2$ to $R+N+1$: line $i+R+1$ contains three space-separated integers $R_s$, $C_s$, and $D_s$ describing the $i$-th stomp-digging instruction.

• A single integer: the total volume of water the lake holds, in cubic inches.