


			MASINI
		       --------

	Se reprezinta in plan, prin coordonate intregi, pozitiile a n masini M1,M2,..,Mn. Pentru
i, 1<=i<=n, masina Mi are in rezervor Ci litri de benzina, un litru fiindu-i suficient pentru a se
deplasa cu Di unitati de lungime pe orizontala si pe verticala (paralel cu axele de coordonate).
Secventa de numere de masini (i1,..,ik) formeaza un parcurs de lungime k daca:

	- masina cu numarul i1 parcurge distanta intre locul sau initialsi locul initial al masinii
cu numarul i2 numai cu benzina care se afla in rezervorul sau.
	- masina i(j) parcurge distanta dintre locul sau initial si locul initial al masinii cu nu-
marul i(j+1) cu benzina care se afla initial in rezervorul sau, la care se adauga cantitatea ramasa
in rezervorul masinii avand numarul i(j-1), pentru 1<j<k.

	Capacitatea rezervoarelor se considera nelimitata. Sa se scrie un program care sa determi-
ne un parcurs de lungime maxima, cu consum minim de benzina.

	Fisierul de intrare, al carui nume se citeste de la tastatura, contine seturi de date sepa-
rate prin cate o linie goala. Un set de date are urmatoarea structura:

	- pe prima linie apare numarul n de masini
	- fiecare din urmatoarele n linii contine numerele ai,oi,ci,di, unde ai,oi sunt abscisa
respectiv ordonata masinii Mi, iar ci,di au semnificatia de mai sus.

	Fisierul de iesire, al carui nume se citeste de la tastatura, va contine pentru fiecare set
de date trei linii:

	- pe prima linie: numarul setului de date de intrare
	- pe a doua linie: parcursul gasit
	- pe a treia linie: consumul de benzina