Farmer John quiere ayuda de vacas para crear un lago. Mapea pastizal en $R$ filas ($3\le R\le100$), $C$ columnas ($3\le C\le100$), cuadrados de seis por seis pies, altura media en pulgadas ($10\le elev_{rc}\le5000$).

Entrena «excavar pisando». Manada fuerte cubre justo $3\times3$ celdas, va a esquina superior izquierda $R_s,C_s$ ($1\le R_s\le R-2;1\le C_s\le C-2$), y baja terreno $D_s$ pulgadas ($1\le D_s\le40$). Vacas más bajas esperan que otras alcancen su nivel. No siempre se pisan todas, o unas menos.

Alturas iniciales, $N$ instrucciones ordenadas ($1\le N\le20000$), nivel final $E$ ($0\le E\le5000$): halla volumen en pulgadas cúbicas, no supera $2,000,000,000$. Barreras en bordes evitan desbordar.

Pastizal $4\times6$, alturas con números de fila/columna:

Colina arriba derecha $36$, pequeña arriba izquierda $28$, depresión ligera medio fila $4$. Tras "$1\;4\;4$":

Solo tres celdas bajan, otros seis grupos esperaban su nivel pero no llegó. Tras "$1\;1\;10$" arriba izquierda:

Nivel $22$ pulgadas da profundidades:

Suma $66$ por área seis por seis pies: $66\times72\times72=342,144$ pulgadas cúbicas, lado $72$ pulgadas.

Escribe programa que automatice cálculo.

Entrada

• Línea $1$: $R,C,E,N$ separados por espacios.

• Líneas $2,\ldots,R+1$: línea $i+1$, fila $i$ con $C$ enteros separados por espacios.

• Líneas $R+2,\ldots,R+N+1$: línea $i+R+1$, instrucción $i$ con $R_s,C_s,D_s$.

Salida

• Línea 1: entero, volumen del nuevo lago en pulgadas cúbicas.

Ejemplos

Entrada 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

Salida 1

342144

Nota

Como ejemplo del texto.

Autor: Rob Kolstad, 2008