НЛО
Служба безпеки Землі прагне знищити корабель ворожих інопланетян. Корабель вже пошкоджено і змушено приземлитися в пустелі. Він складається з кубічних відсіків одиничного розміру, а його нижній шар має форму прямокутника розміром 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.
Примітка
На другому рисунку показано стан корабля, намальованого на першому рисунку, після пострілів лазерів, описаних у прикладі.