Farmer John は牛と湖を作りたいです。牧草地を $R$ 行（$3\le R\le100$）$C$ 列（$3\le C\le100$）、各六フィート四方に分け、平均標高をインチで測りました（$10\le elev_{rc}\le5000$）。
「踏んで掘る」訓練をしました。強い群れがぴったり $3\times3$ マスを覆い、左上 $R_s,C_s$（$1\le R_s\le R-2;1\le C_s\le C-2$）へ移り、$D_s$ インチ（$1\le D_s\le40$）下げます。低い牛は他が同じ高さまで下がるまで踏まず、全マスが踏まれるとは限らず、程度も違います。
初期標高、順序つき $N$ 指示（$1\le N\le20000$）、最終水位 $E$（$0\le E\le5000$）から立方インチの水量を求めます。答え $2,000,000,000$ 以下。縁は障壁で水は流れ出ません。
$4\times6$ の初期標高を行列番号つきで示します：
| 行/列 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $28$ | $25$ | $20$ | $32$ | $34$ | $36$ |
| $2$ | $27$ | $25$ | $20$ | $20$ | $30$ | $34$ |
| $3$ | $24$ | $20$ | $20$ | $20$ | $20$ | $30$ |
| $4$ | $20$ | $20$ | $14$ | $14$ | $20$ | $20$ |
右上丘は $36$、左上小丘は $28$、行 $4$ の中間は少し低いです。指示 "$1\;4\;4$" 後：
| 行 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $28$ | $25$ | $20$ | $32$ | $32$ | $32$ |
| $2$ | $27$ | $25$ | $20$ | $20$ | $30$ | $32$ |
| $3$ | $24$ | $20$ | $20$ | $20$ | $20$ | $30$ |
| $4$ | $20$ | $20$ | $14$ | $14$ | $20$ | $20$ |
三マスだけ下がり、他の六群は同じ高さになるのを待ちますが届きません。次の "$1\;1\;10$" で左上を踏むと：
| 行 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $18$ | $18$ | $18$ | $32$ | $32$ | $32$ |
| $2$ | $18$ | $18$ | $18$ | $20$ | $30$ | $32$ |
| $3$ | $18$ | $18$ | $18$ | $20$ | $20$ | $30$ |
| $4$ | $20$ | $20$ | $14$ | $14$ | $20$ | $20$ |
水位 $22$ インチなら深さは：
| 行 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $4$ | $4$ | $4$ | -- | -- | -- |
| $2$ | $4$ | $4$ | $4$ | $2$ | -- | -- |
| $3$ | $4$ | $4$ | $4$ | $2$ | $2$ | -- |
| $4$ | $2$ | $2$ | $8$ | $8$ | $2$ | $2$ |
合計深さ $66$ に六フィート四方の面積を掛け、$66\times72\times72=342,144$ 立方インチ、各辺 $72$ インチです。
計算を自動化するプログラムを書きます。
入力
行 $1$：空白区切り $R,C,E,N$。
行 $2,\ldots,R+1$：行 $i+1$ に格子行 $i$ の $C$ 整数、空白区切り。
行 $R+2,\ldots,R+N+1$：行 $i+R+1$ は指示 $i$ の $R_s,C_s,D_s$。
出力
入出力例
入力 1
4 6 22 2
28 25 20 32 34 36
27 25 20 20 30 34
24 20 20 20 20 30
20 20 14 14 20 20
1 4 4
1 1 10
出力 1
342144
注記
本文の例のとおりです。
問題作成：Rob Kolstad、2008年