Fişierul intrare/ieşire:	echipe2.in, echipe2.out	Sursă	Algoritmiada 2009, Runda Finala
Autor	Cosmin Gheorghe	Adăugată de	Gheorghe Cosmin •gcosmin
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Echipe2

In momentul in care trimiti o sursa, vei putea vedea scorul obtinut pe o parte din testele folosite la evaluare in monitor.

Julieta este antrenoare de un sport mai ciudat. In acest sport exista N functii pe care un jucator le poate indeplini. Fiecare jucator e expert la o anumita functie si nu poate ocupa decat acea functie. Julieta are cate 2 jucatori pentru fiecare functie si vrea sa formeze doua echipe cat mai echilibrate. Ea cunoaste pentru fiecare dintre cei 2 * N jucatori valoarea acestora (un numar natural). Se defineste dezechilibrul unei echipe ca fiind diferenta dintre cel mai valoros jucator din echipa si cel mai putin valoros. Julieta mai defineste dezechilibrul total ca fiind maximul dintre dezechilibrul primei echipe si dezechilibrul celei de a doua echipa. Pentru ca sunt foarte multi jucatori pe teren, Julieta va roaga pe voi sa aflati care este dezechilibrul total minim pe care il poate obtine.

Date de intrare

Fişierul de intrare echipe2.in va contine pe prima linie numarul N. Urmatoarele N linii vor contine fiecare cate doua numere naturale reprezentand valorile jucatorilor ce pot ocupa functia respectiva.

Date de ieşire

În fişierul de ieşire echipe2.out veti afisa dezechilibrul total minim ce se poate obtine.

Restricţii si precizari

• 1 ≤ N ≤ 10⁵
• Valorile jucatorilor nu vor depasi 10⁹

Exemplu

Explicaţie

O solutie posibila este (valorile ingrosate reprezinta o echipa iar cele neingrosate cealalta echipa):

• 1 3
• 5 4
• 3 4
• 6 5
• 4 2

Dezechilibrul echipei ingrosate este 4, iar dezechilibrul celeilalte echipe este 3. Dezechilibrul total este 4. Pot exista mai multe solutii de a forma echipele

Cum se trimit solutii?