Farmer John veut que les vaches l’aident à créer un lac. Pâturage découpé en $R$ lignes ($3\le R\le100$), $C$ colonnes ($3\le C\le100$) de carrés de six pieds sur six, altitude moyenne en pouces ($10\le elev_{rc}\le5000$).

Il les entraîne à « creuser en piétinant ». Le troupeau robuste couvre exactement $3\times3$ cases, coin supérieur gauche $R_s,C_s$ ($1\le R_s\le R-2;1\le C_s\le C-2$), et abaisse le sol de $D_s$ pouces ($1\le D_s\le40$). Les vaches plus bas attendent que les autres rejoignent leur niveau. Donc toutes les cases ne sont pas forcément piétinées, ou certaines moins.

Altitudes initiales, $N$ instructions ordonnées ($1\le N\le20000$), niveau final $E$ ($0\le E\le5000$) : trouvez le volume en pouces cubes, garanti au plus $2,000,000,000$. Des barrières au bord empêchent le débordement.

Petit pâturage $4\times6$, altitudes avec numéros de lignes/colonnes :

Colline supérieure droite $36$, petite supérieure gauche $28$, légère dépression au milieu de ligne $4$. Après "$1\;4\;4$" :

Seules trois cases baissent ; les six autres groupes attendent leur niveau sans qu’il soit atteint. Après "$1\;1\;10$" en haut à gauche :

Pour niveau $22$ pouces, profondeurs :

Somme $66$, multipliée par six pieds sur six : $66\times72\times72=342,144$ pouces cubes, côtés de $72$ pouces.

Écrivez un programme automatisant le calcul.

Entrée

• Ligne $1$ : $R,C,E,N$ séparés par espaces.

• Lignes $2,\ldots,R+1$ : ligne $i+1$, rangée $i$ avec $C$ entiers séparés par espaces.

• Lignes $R+2,\ldots,R+N+1$ : ligne $i+R+1$, instruction $i$ avec $R_s,C_s,D_s$.

Sortie

• Ligne 1 : entier, volume du nouveau lac en pouces cubes.

Exemples

Entrée 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

Sortie 1

342144

Remarque

Selon l’exemple du texte.

Auteur : Rob Kolstad, 2008