Fişierul intrare/ieşire:cutii.in, cutii.outSursăad-hoc
AutorDin FolclorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.3 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Cutii (clasele 9-10)

Ion are N tipuri de cutii paralelipipedice de dimensiuni cunoscute. Există un număr infinit de cutii din fiecare tip. Ion vrea să construiască un turn cât mai înalt punând cutii una peste alta după următoarele reguli:

  • O cutie cu dimensiunile bazei a x b poate fi pusă peste alta cu dimensiunile bazei c x d numai dacă baza primei cutii se încadrează complet în baza celei de-a doua, aşadar a < c şi b < d.
  • Cutiile pot fi rotite. Cu alte cuvinte, o cutie cu dimensiunile 1×2x3 poate fi folosită şi cu dimensiunile 2×1x3, 3×2x1 etc.

Aflaţi înălţimea maximă a unui turn de cutii.

Date de intrare

Fişierul de intrare cutii.in conţine pe prima linie numărul de tipuri de cutii, N. Pe următoarele N linii se află câte trei numere întregi, despărţite prin spaţiu, indicând dimensiunile unui tip de cutie.

Date de ieşire

În fişierul de ieşire cutii.out se va scrie un singur număr, reprezentând înălţimea maximă a unui turn ce poate fi construit conform regulilor.

Restricţii

  • 1 ≤ N ≤ 2.000
  • Dimensiunile cutiilor sunt cuprinse între 1 şi 1.000.000.000.

Exemplu

cutii.incutii.outExplicaţie
3
5 7 4
6 2 8
1 3 5
20
Aşezăm una peste alta cutiile:
1×3 de înălţime 5;
2×6 de înălţime 8;
4×7 de înălţime 5;
6×8 de înălţime 2.
Trebuie sa te autentifici pentru a trimite solutii. Click aici