Diffusione

In un quartiere, ogni abitante copia il colore delle case dipinte di grigio. Così, il giorno in cui alcune case vengono dipinte di grigio, ogni vicino che abita accanto a una di esse in orizzontale o in verticale decide di dipingere la propria casa allo stesso modo. Ci vuole un mese. Dopodiché, anche le case che si trovano accanto a queste in orizzontale o in verticale decidono di fare lo stesso, e impiegano anch’esse un mese, e così via.

####X        ##XXX       #XXXX        XXXXX
##X##        #XXXX       XXXXX       XXXXX
#####         ##X##       #XXXX        XXXXX
 Mo.1            Mo.2           Mo.3           Mo.4

Come puoi vedere, all’inizio solo due case sono dipinte di grigio ([1,5] e [2,3]). Dopo un mese, 8 case sono dipinte di grigio: quelle sopra, sotto, a destra e a sinistra delle case già dipinte. Dopo due mesi, 13 case sono dipinte di grigio e dopo 3 mesi tutte le case del quartiere sono dipinte di grigio.

In input vengono forniti due numeri naturali H e W, che rappresentano l’altezza e la larghezza del quartiere. Nella riga successiva viene fornito un numero naturale N, che rappresenta il numero di case da dipingere di grigio. Nella riga seguente viene fornito un numero naturale M; nelle successive M righe vengono forniti due numeri naturali X e Y, che rappresentano le posizioni delle case già dipinte di grigio.

Scrivi in output quanti mesi sono necessari per dipingere di grigio un totale di N case (incluse quelle dipinte inizialmente).

Input
3 5
7
2
1 5
2 3

Output
1

Spiegazione #1: L’esempio è quello riportato nel testo qui sopra. Quindi, il quartiere ha un’altezza di 3 e una larghezza di 5. Dobbiamo scrivere in output quanti mesi sono necessari per dipingere di grigio un totale di 7 case. Ci sono già 2 case dipinte di grigio, nelle posizioni [1, 5] e [2,3]. È necessario un mese per dipingere di grigio un totale di 7 case.