În oraş tocmai s-au deschis două mall-uri, însă nu sunt tocmai apropiate. Locuitorii au înaintat o mulţime de petiţii, prin care au cerut un mijloc de transport în comun între cele două locaţii. Primarul, o persoană foarte înţelegătoare, s-a hotărât să rezolve această problemă cât mai repede cu putinţă.
Analizând harta, primarul a observat că oraşul are forma unui grid format din străzi verticale şi orizontale, distanţa dintre oricare două străzi verticale consecutive, respectiv dintre oricare două străzi orizontale consecutive fiind aceeasi. Atât străzile orizontale, cât şi străzile verticale sunt numerotate cu numere naturale consecutive, începând cu 0. O poziţie pe hartă este identificată prin două numere (x, y) unde x reprezintă numărul străzii orizontale, iar y numărul străzii verticale la intersecţia cărora se află poziţia respectivă. Unul dintre mall-uri este situat la poziţia (0,0), iar celălalt la poziţia (a,b).
Însă lucrurile nu sunt aşa de simple. Din motive de buget, trebuie ca traseul pe care se va deplasa mijlocul de transport să fie de lungime minimă. Dar, în acelaşi timp primarul doreşte să uşureze şi accesul în oraş pentru anumite puncte cheie intermediare, diferite de cele corespunzătoare celor două mall-uri. În acest sens, a selectat N astfel de puncte intermediare distincte şi a stabilit că traseul care va uni cele două mall-uri trebuie să aibă lungime totală minimă; iar dintre traseele de lungime minimă posibile, primarul va alege un traseu care să treacă prin cât mai multe dintre cele N puncte cheie intermediare.
Cerinţă
Să se determine numărul maxim de puncte cheie intermediare prin care poate trece un traseu de lungime minimă care uneşte cele două mall-uri.
Date de intrare
Fişierul de intrare bus.in conţine pe prima linie două numere naturale separate prin spaţiu, reprezentând coordonatele a şi b. Pe linia a doua se află numărul natural N, iar pe fiecare dintre următoarele N linii se află câte două numere naturale separate prin spaţiu reprezentând coordonatele x y ale celor N puncte cheie intermediare.
Date de ieşire
Fişierul de ieşire bus.out va conţine o singură linie pe care va fi scris numărul maxim de puncte cheie intermediare prin care poate trece un traseu de lungime minimă care va uni cele două mall-uri.
Restricţii
1 <= N <= 100 000
0 <= a <= 2 000 000 000 şi 0 <= b <= 2 000 000 000
0 <= x[i] <= a
0 <= y[i] <= b
20% dintre teste vor avea a <= 1 000 şi b <= 1 000
50% dintre teste vor avea N <= 1 000
Mijlocul de transport se deplasează numai pe străzi.
Exemple
bus.in
bus.out
Explicaţie
10 6
4
2 1
9 2
4 5
6 3
2
Justificare: Un traseu posibil este cel din figura de mai jos
