Harta unui continent poate fi văzută ca un dreptunghi având înălţimea de M unităţi, iar lăţimea de N unităţi. Colţul din stânga sus al hărţii are coordonatele (0,0), iar colţul din dreapta jos are coordonatele (M,N). Coordonatele oraşelor de pe hartă sunt întotdeauna numere întregi, adică sunt de forma (l,c) cu 0≤l≤M, reprezentând linia şi 0≤c≤N, reprezentând coloana. În unul din oraşele de pe hartă se găseşte un turist. El doreşte să pornească într-o expediţie deosebită. A decis să plece într-o anumită direcţie, şi să păstreze aceea direcţie pănă ajunge la marginea continentului (a hărţii) unde se încheie expediţia sa. Doreşte însă să aleagă acea direcţie care îl asigură că pe drumul său va trece prin cât mai multe oraşe.
Cerinţă
Dându-se dimensiunile hărţii, coordonatele oraşului în care se găseşte turistul şi coordonatele tuturor celorlalte oraşe de pe hartă, se cere să se determine numărul maxim de oraşe pe care le va vizita turistul.
Date de intrare
Pe prima linie a fişierului de intrare turist.in se găsesc numerele naturale M N separate printr-un spaţiu reprezentând dimensiunile hărţii. A doua linie a fişierului conţine două numere naturale l şi c separate printr-un spaţiu, reprezentând poziţia iniţială a turistului pe hartă. Linia a treia a fişierului conţine un număr natural k, reprezentând numărul de oraşele de pe hartă, diferite de oraşul în care se găseşte turistul.
Pe următoarele k linii se găsesc câte două numere naturale, separate printr-un spaţiu, reprezentând coordonatele câte unui oraş de pe hartă, altele decât cel în care se găseşte turistul.
Date de ieşire
Fişierul de ieşire turist.out va avea pe prima sa linie, un număr natural reprezentând numărul maxim de oraşe pe care le vizitează turistul.
Restricţii
1 ≤ M ≤ 1000
1 ≤ N ≤ 1000
1 ≤ k ≤ 2000
Exemple
turist.in
turist.out
Explicaţii
5 10
3 2
7
0 0
0 8
1 6
2 2
2 4
3 7
4 5
3
Datele de intrare corespund hărţii din figura următoare. Traseul ales este cel indicat de linia trasată.
