Göbələklər#5438
Maşa nənəsini ziyarət etməyə qərar verdi. O, özü ilə iki səbət götürdü: biri pirojkilərlə dolu, digəri isə yolda toplamaq istədiyi göbələklər üçün boşdur.
Nənəsinə çatmaq üçün Maşa m \times n ölçüsündə olan meşədən keçməlidir. Bu meşədə bəzi hüceyrələrdə ağaclar, bəzilərində isə göbələklər bitir. Maşa hüceyrəsindən başlayır və nənəsinin yerləşdiyi kəndə, yəni hüceyrəsinə doğru gedir. Hər addımında Maşa yalnız sağa və ya aşağıya hərəkət edə bilər (yəni koordinatlarından birini və yalnız birini artırır), əgər bu hərəkətdən sonra olduğu hüceyrədə ağac yoxdursa. Əgər həm sağda, həm də aşağıda ağac varsa, Maşa azmış hesab olunur.
Verilmiş meşəyə əsasən, Maşanın azmadan nənəsinə çata biləcəyini və əgər bacararsa, bu zaman maksimum neçə göbələk toplaya biləcəyini müəyyən etməlisiniz.
Giriş faylının ilk sətirində dörd ədəd , , , (2 \le m, n \le 100, 0 \le g, t \le g + t \le m n - 2) verilmişdir. Növbəti sətirdə hər birində 2 ədəd — -ci göbələyin və koordinatları yerləşir. Onlardan sonra ağacların təsviri eyni formatda sətirdə verilir. Heç bir hüceyrədə bir göbələkdən çox, eyni anda göbələk və ağac, yaxud bir ağacdan çox bitə bilməz. Bundan əlavə, və hüceyrələrində heç nə bitmir.
Əgər Maşa nənəsinə çata bilirsə, çıxış faylının ilk sətirində bu zaman toplaya biləcəyi maksimum göbələk sayı verilməlidir, növbəti m+n-1 sətirdə isə Maşanın ardıcıl ziyarət etdiyi hüceyrələrin koordinatları x_i y_i formatında verilməlidir, maksimum göbələk toplanan yol üçün. Əgər belə yollar bir neçədirsə, aşağıya enən yol verilməlidir.
Əks halda çıxış faylında tək bir ədəd verilməlidir.
Nümunə 1
Nümunə 2