НЛО#7472

НЛО

2 секунди

64 мегабайти

Середня

Служба безпеки Землі прагне знищити корабель ворожих інопланетян. Корабель вже пошкоджено і змушено приземлитися в пустелі. Він складається з кубічних відсіків одиничного розміру, а його нижній шар має форму прямокутника розміром $n \times m$ n \times m. На рисунку показано приклад вигляду зверху на корабель розміром $n = 4$ n = 4, $m = 8$ m = 8.

Відсіки корабля виготовлені з надміцного металу, тому для їх руйнування використовуються лазери. Лазерні установки розгорнуті з чотирьох боків корабля і періодично випускають промені, перпендикулярні до сторін корабля, спрямовані на різні відсіки. Кожен промінь руйнує $r$ перших відсіків, що трапляються на його шляху. Якщо над знищеним відсіком є інші, вони опускаються вниз.

Після $k$ пострілів було вирішено завдати авіаудар по кораблю. Для удару потрібно вибрати таку ділянку розміром $p \times p$ p \times p, яка містить максимальну кількість уцілілих відсіків, щоб знищити їх усі.

Напишіть програму, яка обчислить максимальну кількість цілих блоків, які можна знищити авіаударом на ділянці розміром $p \times p$ p \times p.

Вхідні дані

У першому рядку подано $5$ цілих чисел: $n$ , $m$ ( $1 \leq n \cdot m \leq 1000000$ 1 \leq n \cdot m \leq 1\,000\,000), $r$ ( $0 < r \leq 10$ 0 < r \leq 10), $k$ ( $0 < k \leq 300000$ 0 < k \leq 300\,000) і $p$ ( $0 < p \leq min (n, m, 10)$ 0 < p \leq \min(n, m, 10)). У кожному з наступних $n$ рядків записано по $m$ чисел. Число в $i$ -му рядку і $j$ -му стовпці описує кількість одиничних блоків у відповідній частині корабля, аналогічно рисунку. Кожне число знаходиться в діапазоні $1 \dots 1 0^{6}$ 1 \ldots 10^6.

У наступних $k$ рядках описані постріли з лазерів. Кожен з цих рядків містить один символ і через пробіл два числа. Символи визначають сторону впливу: "W" - захід, "E" - схід, "S" - південь, "N" - північ. Перше число визначає номер рядка у випадку заходу і сходу або стовпця у випадку півночі і півдня, а друге - номер шару по висоті, в який робиться постріл. Рядки і стовпці відповідають нумерації з вхідних даних, шари нумеруються з одиниці. Кожне число знаходиться в діапазоні $1 \dots 1 0^{6}$ 1 \ldots 10^6.

Вихідні дані

Виведіть максимальну кількість уцілілих відсіків після $k$ пострілів лазерами на ділянці розміром $p \times p$ p \times p.

Приклади

Приклад 1

Примітка

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