Dünyanın təhlükəsizlik xidməti düşmən mövqedə duran yadplanetlilərin hava gəmisini məhv etmək istəyir. Təhlükəsizlik xidməti artıq hava gəmisini zədələmiş və onu səhraya enməsinə məcbur etmişdir. Hava gəmisi vahid ölçülü kubvari bölmələrdən ibarətdir və alt təbəqəsi n × m ölçülü düzbucaqlı formasındadır. Şəkildə n = 4, m = 8 ölçülü hava gəmisinin üstən görünüşünə aid nümunə verilmişdir.

Hava gəmisinin bölmələri yüksəkdavamlılıqlı metaldan hazırlanmışdır və buna görə də onun dağıdılması üçün lazerdən istifadə edilir. Lazer qurğuları hava gəmisinin dörd yan tərəfinin qarşısında yerləşdirilmişdir və onlar dövrü olaraq hava gəmisinin tərəflərinə perpendikulyar olan və gəminin müxtəlif bölmələri istiqamətində şüalar buraxırlar. Hər bir şüa onun yolunda yerləşən ilk r sayda bölməni məhv edir. Məhv edilmiş bölmənin üzərində digər bölmələr olarsa, onlar aşağı doğru sürüşdürülür.

k sayda atəşdən sonra hava gəmisənə aviazərbələr endirmək qərarına gəlindi. Zərbə üçün elə p × p ölçülü sahə seçmək lazımdır ki, onların hamısını məhv etmək üçün nişan alınmış maksimal sayda bölmə ehtiva etsin. p × p ölçülü sahəyə endirilmiş aviazərbənin nə qədər tam bloku məhv edəcəyini hesablayan proqramı tərtib etməli.

Giriş verilənləri

İlk sətirdə 5 tam ədəd: n, m (1 ≤ n ∙ m ≤ 1 000 000), r (0 < r ≤ 10), k (0 < k ≤ 300 000) və p (0 < p ≤ min(n, m, 10)) verilir. Növbəti n sətrin hər birində m sayda ədədlər verilir. i-ci sətrin j-ci sütunundakı ədəd şəkildə verildiyi kimi hava gəmisinin uyğun sahəsindəki vahid blokların sayını əks etdirir. Hər bir ədəd 1..10^6 diapazonundadır.

Növbəti k sətirdə lazer atəşləri təsvir edilib. Bu sətirlərdən hər biri bir simvol ehtiva edir və ondan sonra boşluqla ayrılmış iki ədəd verilir. Simvollar təsir istiqamətlərini ifadə edirlər: “W” – qərb, “E” – şərq, “S” – cənub, “N” – şərq. İlk ədəd atəşin açıldığı qərb və şərq halında sətirin nömrəsini və ya şimal və cənub halında isə təbəqənin yüksəklik nömrəsini ifadə edir. Sətir və sütunlar giriş verilənlərinə uyğun nömrələnir təbəqələr isə birdən başlayaraq nömrələnir. Hər bir ədəd 1..10^6 diapazonunda verilir.

Çıxış verilənləri

p × p ölçülü sahədə k sayda atəşdən sonra nişan alınmış bölmələrin maksimal sayını verməli.

Şərh

İkinci şəkildə misalda göstərildiyi kimi lazer atəşlərindən sonra birinci şəkildə verilmiş hava gəmisinin vəziyyəti verilmişdir.