== include(page="template/taskheader" task_id="centrale") ==

In tara Smecheriei s-au construit $N$ centrale nucleare, numerotate de la $1$ la $N$, pentru a furniza enrgie electrica intregii tari. Fiecare centrala $i$ se afla la pozitia $(x[~i~],y[~i~])$ in plan. In ciuda smecheriei populatiei tarii, acestia nu s-au hotarat si pe care centrale o sa le puna in functiune, doar stiu ca in functie de constructia si amplasarea acestora exista $M$ restrictii de forma: cel putin una din centralele $a$ si $b$ trebuie puse in functiune. Datorita banului gros de care dau dovada cetatenii acestei tari, nu s-a pus problema sigurantei si utilitatii acestor centrale inainte de constructie si, prin urmare, cateva centrale nu vor fi folosite din cauza sigurantei. Scopul vostru este sa determinati distanta maxima $D$ astfel incat sa se poata alege o multime de centrale care sa fie puse in functiune astfel incat, din motive de siguranta, distanta Manhattan intre oricare doua centrale alese sa fie mai mare sau egala cu $D$.

In tara Smecheriei s-au construit $N$ centrale nucleare pentru a furniza enrgie electrica intregii tari. Fiecare centrala $i$ se afla la pozitia $(x[~i~],y[~i~])$ in plan. In ciuda smecheriei populatiei tarii, acestia nu s-au hotarat si pe care centrale o sa le puna in functiune, doar stiu ca in functie de constructia si amplasarea acestora exista $M$ restrictii de forma: cel putin una din centralele $a$ si $b$ trebuie puse in functiune. Datorita banului gros de care dau dovada cetatenii acestei tari, nu s-a pus problema sigurantei si utilitatii acestor centrale inainte de constructie si, prin urmare, cateva centrale nu vor fi folosite din cauza sigurantei. Scopul vostru este sa determinati distanta maxima $D$ astfel incat sa se poata alege o multime de centrale care sa fie puse in functiune astfel incat, din motive de siguranta, distanta Manhattan intre oricare doua centrale alese sa fie mai mare sau egala cu $D$.

h2. Date de intrare