poarta

Se consideră harta universului ca fiind o matrice cu $250$ de linii şi $250$ de coloane. În fiecare celulă se găseşte o aşa numită poartă stelară, iar în anumite celule se găsesc echipaje ale porţii stelare. La o deplasare, un echipaj se poate deplasa din locul în care se află în oricare alt loc în care se găseşte o a doua poartă, în cazul nostru în orice altă poziţie din matrice. Nu se permite situarea simultană a mai mult de un echipaj într-o celulă. La un moment dat un singur echipaj se poate deplasa de la o poartă stelară la alta.

Cerință

Dându-se un număr $p$ de echipaje, pentru fiecare echipaj fiind precizate poziţia iniţială şi poziţia finală, determinaţi numărul minim de deplasări necesare pentru ca toate echipajele să ajungă din poziţia iniţială în cea finală.

Date de intrare

Fișierul de intrare poarta.in are următorul format:

• pe prima linie se află numărul natural $p$ reprezentând numărul echipaje.
• pe următoarele $p$ linii se află câte 4 numere naturale, primele două reprezentând coordonatele poziţiei iniţiale a unui echipaj (linie respectiv coloană), următoarele două reprezentând coordonatele poziţiei finale a aceluiaşi echipaj (linie respectiv coloană).

Date de ieşire

Pe prima linie a fişierului de ieșire poarta.out se scrie un singur număr reprezentând numărul minim de deplasări necesar.

Restricții și precizări

• $1 < p < 5\ 000$
• Coordonatele poziţiilor iniţiale şi finale ale echipajelor sunt numere naturale din intervalul $[1, 250]$.
• Atenție la cazurile când poziția inițială este identică cu cea finală!
• Poziţiile iniţiale ale celor $p$ echipaje sunt distincte două câte două.
• Poziţiile finale ale celor $p$ echipaje sunt distincte două câte două.

Exemplu

poarta.in

3
1 2 3 4
6 5 3 9
3 4 1 2

poarta.out

4

Explicație