Farmer John chce z krowami stworzyć jezioro. Mapuje pastwisko $R$ rzędów ($3\le R\le100$), $C$ kolumn ($3\le C\le100$) kwadratów sześć na sześć stóp, średnia wysokość w calach ($10\le elev_{rc}\le5000$).

Uczy „kopania tupaniem”. Silne stado pokrywa dokładnie $3\times3$, idzie do lewego górnego $R_s,C_s$ ($1\le R_s\le R-2;1\le C_s\le C-2$), obniża o $D_s$ cali ($1\le D_s\le40$). Niższe czekają aż reszta osiągnie ich poziom. Nie wszystkie są tupane albo niektóre mniej.

Wysokości, uporządkowane $N$ instrukcji ($1\le N\le20000$), poziom $E$ ($0\le E\le5000$): objętość w calach sześciennych najwyżej $2,000,000,000$. Bariery na brzegach zapobiegają wypływaniu.

Pastwisko $4\times6$, wysokości z rzędami/kolumnami:

Wzgórze góra prawo $36$, małe góra lewo $28$, lekka niecka środka rzędu $4$. Po "$1\;4\;4$":

Tylko trzy komórki obniżone, sześć grup czekało na poziom, który nie nadszedł. Po "$1\;1\;10$" góra lewo:

Poziom $22$ cali daje głębokości:

Suma $66$ razy sześć na sześć stóp: $66\times72\times72=342,144$ cali sześciennych, bok $72$ cale.

Napisz program automatyzujący.

Wejście

• Wiersz $1$: $R,C,E,N$ ze spacjami.

• Wiersze $2,\ldots,R+1$: wiersz $i+1$, rząd $i$ z $C$ całkowitymi ze spacjami.

• Wiersze $R+2,\ldots,R+N+1$: wiersz $i+R+1$, instrukcja $i$ z $R_s,C_s,D_s$.

Wyjście

• Wiersz 1: całkowite, objętość jeziora w calach sześciennych.

Przykład

Wejście 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

Wyjście 1

342144

Uwagi

Jak w przykładzie tekstu.

Autor: Rob Kolstad, 2008