Boya#3039
Olimpiya planetində ənənəvi illik "Boya" oyunu keçirilir. Oyun N \times M ölçülü böyük bir sahədə oynanır və hər bir hüceyrə əvvəlcədən ya ağ, ya da qara rəngə boyanıb. İki oyunçu növbə ilə oynayır, cəmi dəqiq gediş edilir. Hər gedişdə oyunçu, istənilən bir düzbucaqlının (hündürlüyü və eni -dən böyük olmamaq şərtilə), bütün hüceyrələrini öz rəngi ilə təkrar rəngləyə bilər. Birinci oyunçu hüceyrələri ağ, ikinci oyunçu isə qara rəngə boyayır. -cı gedişdən sonra yekun hesab, son təsvirə görə hər rəngdə olan hüceyrələrin sayı ilə müəyyən edilir. Öz rəngində daha çox hüceyrə olan oyunçu qalib gəlir. Hər iki oyunçu optimal oynayarsa, məqsəd, son vəziyyətdə öz rəngində olan hüceyrələrin sayını maksimum etməkdir.
Verilişə görə, başlanğıc boyanmanı, gedişlərin sayını və boyanacaq düzbucaqların maksimal ölçüsünü nəzərə alaraq, hər iki oyunçunun optimal oynadığı halda, son vəziyyətdə hər rəngdə neçə hüceyrə olduğunu müəyyən edən proqram yazın.
Birinci sətirdə dörd müsbət tam ədəd verilir: , , , və (N \leq 400, M \leq 400, D \leq 400, K \leq 10^9) — sahənin hündürlüyü və eni, bir gedişdə boyana bilən düzbucağın maksimal ölçüsü və ümumi gediş sayı. Sonrakı sətrin hər birində simvol olur: uyğun hüceyrə ağdırsa , qaradırsa .
Bir sətirdə iki tam ədəd çap edin — hər iki oyunçu optimal oynadıqda, son vəziyyətdə sahədə olan ağ və qara hüceyrələrin sayı.
Nümunə 1