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

Un grup de $N$ studenti a venit la facultate sa dea un examen si exista $3$ sali disponibile in care poti fi repartizati. Fiecare student are o anumita inaltime si greutate. Astfel, fiecare student $i$ are inaltimea $H{~i~}$ si greutatea $G{~i~}$. Se pune problema unei repartitii cat mai echilibrate in sali a studentilor. In fiecare sala trebuie repartizat cel putin un student si, in mod evident fiecare student trebuie repartizat intr-o singura sala.

Un grup de $N$ studenti a venit la facultate sa dea un examen si exista $3$ sali disponibile in care poti fi repartizati. Fiecare student are o anumita inaltime si greutate. Astfel, fiecare student $i$ are inaltimea $H{~i~}$ si greutatea $G{~i~}$. Se pune problema unei repartitii cat mai echilibrate in sali a studentilor. In fiecare sala trebuie repartizat cel putin un student si, in mod evident fiecare student trebuie repartizat exact intr-o singura sala. Fie $S1$, $S2$ si $S3$ cele trei sali in care sunt repartizati studenti. O repartitie este cu atat mai echilibrata cu cat valoarea $[Gmax(S1)+Gmax(S2)+Gmax(S3)]*[Hmax(S1)+Hmax(S2)+Hmax(S3)]$ este mai mica (sa numim aceasta valoare echilibrul unei repartitii). $Gmax(S{~i~})$ reprezinta greutatea maxima a unui student din sala $S{~i~}$ iar $Hmax(S{~i~})$ inaltimea maxima. Determinati echilibrul minim posibil al unei repartitii.

h2. Date de intrare

Fişierul de intrare $studenti.in$ ...

Fişierul de intrare $studenti.in$ contine pe prima linie numarul $N$ avand semnificatia din enunt. Urmeaza apoi $N$ linii, pe linia $i+1$ aflandu-se valorile $H{~i~}$ si $G{~i~}$, separate printr-un spatiu.

h2. Date de ieşire

În fişierul de ieşire $studenti.out$ ...

În fişierul de ieşire $studenti.out$ se va afisa pe prima linie echilibrul minim posibil al unei repartitii.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 ≤ N ≤ 300$
* Toate inaltimile studentilor sunt diferite intre ele
* Toate greutatile studentilor sunt diferite intre ele
* $1 ≤ H{~i~}, G{~i~} ≤ 2000$

h2. Exemplu
table(example). |_. studenti.in |_. studenti.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
  1 1
  2 2
  3 3
| 36

|
h3. Explicaţie

...

Avem o singura posibilitate, de a plasa cate un student in fiecare sala, si echilibrul obtinut astfel este (2+3+1)*(2+3+1) = 36.

== include(page="template/taskfooter" task_id="studenti") ==

4302