Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: grybai.in

Rezultatų failas: grybai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Grybai

Stačiakampiame miško plote vyks grybavimo čempionatas. Organizatoriai jį padalino į kvadratinio metro dydžio plotelius bei sudarė visų G miške augančių grybų sąrašą – kiekvienam grybui užrašė plotelio, kuriame jis auga, koordinates. Čempionate varžysis D dalyvių. Siekiant sudaryti kuo panašesnes sąlygas, mišką reikia padalinti į D rėžių taip, kad didžiausias kuriame nors rėžyje esantis grybų skaičius būtų minimalus. Miško padalinimas į rėžius gaunamas padalinant mišką tik vertikaliomis arba tik horizontaliomis linijomis nuo vieno miško krašto iki kito. Kiekvienas kvadratėlis būtinai priklauso lygiai vienam rėžiui ir dalyviui negalima priskirti nulinio ploto rėžio (tačiau dalyviui galima priskirti plotą kuriame nėra nė vieno grybo).

Parašykite programą, kuri pagal miško parametrus, grybų koordinačių sąrašą ir dalyvių skaičių rastų kurį nors optimalų miško padalinimą į rėžius.

Pradiniai duomenys

Pirmoje eilutėje pateikiami sveikieji tarpais atskirti skaičiai X, Y, D ir G (2\\leqX,Y\\leq100000, 2\\leqD\\leqmax(X,Y), 1\\leqG\\leq100000). Šie skaičiai atitinkamai reiškia miško matmenis, dalyvių skaičių, grybų skaičių. Tolesnėse G eilučių yra po du tarpais atskirtus veikuosius skaičius x_i ir y_i (1\\leqx_i\\leqX, 1\\leqy_i\\leqY), nusakančius kvadratėlį, kuriame auga grybas.

Rezultatai

Išveskite vieną skaičių – didžiausią kuriame nors rėžyje esantį grybų skaičių.

Pavydžiai

Pradiniai duomenys Rezultatai 
4 5 2 8
1 1
1 2
1 3
2 1
2 2
2 3
3 4
3 4
 
4