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$, высоты с номерами строк/столбцов:

Справа сверху холм $36$, слева сверху небольшой $28$, середина строки $4$ слегка впала. После "$1\;4\;4$":

Опустились лишь три клетки; остальные шесть групп ждали достижения их уровня, но не дождались. После "$1\;1\;10$" слева сверху:

При воде $22$ дюйма глубины:

Суммарная глубина $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$ содержит $R_s,C_s,D_s$ инструкции $i$.

Выходные данные

• Строка 1: целое, объём нового озера в кубических дюймах.

Примеры

Входные данные 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