Задача №112547. НЛО2
Служба безопасности Земли хочет уничтожить корабль враждебно настроенных инопланетян. Служба безопасности уже повредила корабль и заставила его сесть в пустыне. Корабль построен из кубических отсеков единичного размера и нижний слой имеет форму прямоугольника размером 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 .
4 8 2 6 2 1 1 1 1 1 1 1 1 1 2 3 1 1 1 3 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 2 N 2 W 2 W 2 E 2 S 4 S 7
6