НЛО

Служба безопасности Земли хочет уничтожить корабль враждебно настроенных инопланетян. Служба безопасности уже повредила корабль и заставила его сесть в пустыне. Корабль построен из кубических отсеков единичного размера, и нижний слой имеет форму прямоугольника размером n × m. На рисунке показан пример вида сверху на корабль размером n = 4, m = 8.

Отсеки корабля сделаны из сверхпрочного металла, поэтому для разрушения корабля используются лазеры. Лазерные установки были развернуты напротив четырех боковых сторон корабля, и они периодически выпускают лучи, перпендикулярные сторонам корабля, в сторону различных отсеков корабля. Каждый луч разрушает r первых отсеков, встретившихся на его пути. Если над уничтоженным отсеком находятся другие отсеки, то они сдвигаются вниз.

После k выстрелов было решено нанести по кораблю авиаудар. Для удара имеет смысл выбрать такой участок размером p × p, который целиком содержит максимальное количество уцелевших отсеков, чтобы уничтожить их все.

Напишите программу, которая вычислит, какое количество целых блоков сможет уничтожить авиаудар, нанесенный на участке размером p × p.

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

В первой строке даны 5 целых чисел: n, m (1 ≤ n ∙ m ≤ 1 000 000), r (0 < r ≤ 10), k (0 < k ≤ 300 000) и p (0 < p ≤ min(n,m,10)). В каждой из следующих n строк записаны по m чисел. Число в i-ой строке и j-ом столбце описывает количество единичных блоков в соответствующей части корабля аналогично рисунку. Каждое число находится в диапазоне 1..10^6.

В следующих k строках описаны выстрелы из лазеров. Каждая из этих строк содержит один символ и через пробел от него два числа. Символы определяют сторону воздействия: “W” - запад, “E” - восток, “S” - юг, “N” - север. Первое число определяет номер строки в случае запада и востока или столбца в случае севера и юга, а второе - номер слоя по высоте, в который делается выстрел. Строки и столбцы соответствуют нумерации из входных данных, слои нумеруются с единицы. Каждое число находится в диапазоне 1..10^6.

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

Выведите максимальное количество уцелевших отсеков после k выстрелов лазерами на участке размером p × p.

Примеры

Примечание

На втором рисунке показано состояние корабля, нарисованного на первом рисунке, после выстрелов лазеров, описанных в примере.