Bal üçün döyüş
Vinni Pux bir neçə gün meşədə gəzərkən əvvəllər heç olmadığı bir yerə gəldi. Burada hər hüceyrəsində arı pətəyi olan bir dama düzənliyinə rast gəldi. Vinni bir neçə dəqiqə donub qaldı və danışmaq qabiliyyətini itirdi. Ona elə gəldi ki, cənnətə düşüb. Amma burada nəsə qaydasında deyildi...
Çəpərlər. Çəpərlər. Hasarlar. Bəlkə də, siz Puxun təəccübünü başa düşmürsünüz. Onun səbəbini izah etmək üçün kiçik bir məlumat verək. Arılar, məlum olduğu kimi, çox sadiq həşəratlardır. Əgər kiməsə bağlanırlarsa, uzun müddət yalnız ona xidmət edəcəklər. Pətək isə çəpərlə əhatə olunarsa, bu, arılar üçün böyük bir şərəfdir. Beləliklə, arılara yaxşı niyyətlərinizi, onları qorumaq istəyinizi göstərə bilərsiniz. Axı heç kim çəpəri aşmaz, amma onun olmaması halında, arılara kim istəsə gələ bilər. Arılar bunu mükəmməl başa düşür və ətraflarına bu çəpəri qoyan şəxsə xidmət etməyə başlayırlar.
İndi isə Vinniyə qayıdaq. Çəpərləri görən kimi dərhal nəsə pis bir şeydən şübhələndi. Onlar açıq-aşkar süni mənşəli idilər. Doğrudan da, meşənin ortasında çəpərlər haradan gələ bilər? Rəqibinin olduğunu anlayaraq və heç nə etməsə nə qədər bal itirəcəyini qiymətləndirərək, hərəkət etməyə qərar verdi.
Pux meşədə gizləndi və yerli arıları ələ keçirmək istəyən o yad adamı gözləməyə başladı. Bütün gecəni onu gözləməklə keçirdi, amma səhər bəxti gətirdi. O, düzənliyin əks tərəfindən bir səs eşitdi və öz məqsədləri üçün istifadə etmək niyyəti ilə taxtalar daşıyan yad adamı gördü. Onun bəxtinə, Vinni də yaxşı hazırlaşmışdı. Yəni, bu anda o, artıq üç tərəfdən çəpərlənmiş seçilmiş pətəyə doğru qaçırdı ki, dördüncü çəpəri qoyaraq bu pətəyin arılarını öz tərəfinə çəksin və pətəyi öz nəzarətinə alsın.
Yeni çevrilmiş arılar yeni sahibinə sadiqlik göstərməyə qərar verdilər və Puxun rəqibini əhatə etdilər. Vinni qiymətləndirdi ki, rəqibi bir pətəkdən arılardan qaçarkən, onun özünün daha bir çəpər qoymağa və bəlkə də daha bir pətəyi ələ keçirməyə vaxtı var. Yeni ələ keçirilmiş pətəyin arıları da Vinninin rəqibinə hücum edirlər. Üstəlik, müxtəlif pətəklərin arıları arasında münasibətlər çox da dostcasına deyil, ona görə də Pux bir taxta qoyaraq dərhal iki pətəyi ələ keçirirsə, onun rəqibinə yalnız bir pətək hücum edir. Pux başa düşür ki, rəqibini bu şəkildə uzun müddət saxlaya bilməyəcək və nə qədər pətəyi ələ keçirə biləcəyini öyrənmək istəyir.
Giriş verilənləri
Giriş faylında sahənin konfiqurasiyası verilir. Birinci sətirdə n və m (1 ≤ n, m ≤ 1000) - sahənin ölçüləri verilir. Sahədən kənarda pətəklər yoxdur. İkinci sətirdə artıq çəpərlərlə əhatə olunmuş pətəklərin sayı t verilir.
Sonra t sətirdə onların təsviri verilir. Bu, x_i y_i c_i ... (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 1 ≤ c_i ≤ 4) - ətrafında nəsə olan pətəyin koordinatları, onun ətrafında olan çəpərlərin sayı və sonra ... əvəzinə boşluqla c_i müxtəlif N, S, E, W hərfləri - pətəyin hansı tərəflərinin çəpərləndiyi verilir. N - şimal, S - cənub, E - şərq, W - qərb. x oxu şərqə, y - şimala yönəlib.
Hər bir çəpər iki pətək üçün qonşudur. Məsələn, (x, y) pətəyinin şimal hissəsində çəpər varsa, (x + 1, y) koordinatlı pətəyin cənub hissəsində çəpər olacaq.
Giriş faylında hər bir çəpər hissəsi bir və ya iki dəfə göstərilə bilər. Yəni, əgər (x, y) pətəyinin şimalında çəpər olduğu deyilibsə, (x + 1, y) pətəyi giriş faylında göstərilməyə bilər.
Çıxış verilənləri
Tək bir tam ədəd çıxarın - Vinninin hər tərəfdən çəpərlə əhatə edə biləcəyi maksimum pətək sayı.