Rəngləmə
Planeta Olimpiya hər il ənənəvi "Boyama" oyununu təşkil edir. Bu oyun, N×M ölçüsündə böyük bir olimpiya sahəsində keçirilir və hər bir hüceyrə ya ağ, ya da qara rəngdə boyanmışdır. İki oyunçu növbə ilə oynayır və ümumilikdə K gediş edirlər. Hər oyunçu öz növbəsində hündürlüyü və eni D-dən çox olmayan istənilən bir düzbucaqlının bütün hüceyrələrini öz rənginə boyaya bilər. Birinci oyunçu hüceyrələri ağ rəngə, ikinci oyunçu isə qara rəngə boyayır. K-cı gedişin sonunda oyunun yekun hesabı - hər rəngdəki hüceyrələrin sayı hesablanır. Daha çox hüceyrə rəngləyən oyunçu qalib elan olunur. Buna görə də, hər bir oyunçunun məqsədi sahənin yekun boyama vəziyyətində öz rəngindəki hüceyrələrin sayını maksimuma çatdırmaqdır.
Başlanğıc boyama, gedişlərin sayı və oyunçunun boyaya biləcəyi düzbucaqlının ölçüsünə qoyulan məhdudiyyətlər əsasında oyunun yekun hesabını optimal strategiya ilə tapacaq proqram yazın.
Giriş verilənləri
Birinci sətir dörd natural ədədi ehtiva edir: N, M, D və K (N ≤ 400, M ≤ 400, D ≤ 400, K ≤ 10^9) - sahənin hündürlüyü və eni, oyunçunun boyaya biləcəyi düzbucaqlının ölçüsünə qoyulan məhdudiyyət, yekun hesabın aparılmasına qədər ediləcək gedişlərin sayı. Sonrakı N sətirdə M simvol yerləşir: müvafiq hüceyrə ağ rəngdə boyanıbsa W, sahənin hüceyrəsi qara rəngdə boyanıbsa B.
Çıxış verilənləri
Yeganə sətir iki tam ədəd - hər iki oyunçunun optimal oyun şəraitində yekun boyama variantında ağ və qara hüceyrələrin sayını ehtiva etməlidir.