Vopsea

Time limit: 3s Memory limit: 128MB Input: Output:

Matei are nevoie de vopsea neagră pentru a-și vopsi trotineta. Toată lumea știe că vopseaua neagră se obține amestecând aceeași cantitate de vopsea roșie, galbenă și albastră.

Matei are la dispoziție NN găleți de vopsea deja amestecată. Vopseaua i (1iN)i \ (1 ≤ i ≤ N ) s-a obținut prin amestecarea a rir_i litri de vopsea rosșie, gig_i litri de vopsea galbenă și aia_i litri de vopsea albastră.

Matei dorește să combine unele dintre aceste găleți (posibil niciuna), astfel încât vopseaua obținută să fie neagră.

Cerință

Care este cantitatea maximă (în litri) de vopsea neagră pe care o poate obține?

Date de intrare

Pe prima linie se dă NN , numărul de galeți de vopsea.

Pe următoarele NN linii se vor găsi câte 33 numere, pe linia ii găsindu-se numerele ri,gir_i, g_i și aia_i.

Date de ieșire

Se va afișa un singur număr, respectiv cantitatea maximă de vopsea neagră pe care Matei o poate obține.

Restricții și precizări

  • 1N401 \leq N \leq 40
  • 0ri,gi,ai1060 \leq r_i, g_i, a_i \leq 10^6
  • Am notat S=max{i=1Nai,i=1Nri,i=1Ngi} S = max\{\sum_{i=1}^{N}a_i, \sum_{i=1}^{N}r_i, \sum_{i=1}^{N}g_i\}
# Punctaj Restricții
1 27 1N20,1S501 \leq N \leq 20, 1 \leq S \leq 50
2 36 1N30,1S1001 \leq N \leq 30, 1 \leq S \leq 100
3 37 Fără restricții suplimentare.

Exemplu

stdin

6
1 3 0
10 4 9
2 1 0
0 0 5
1 1 1
2 1 0

stdout

18

Explicație

Dacă alegem gălețile 1,3,4,51, 3, 4, 5 și 66, atunci vom avea câte 66 litri de vopsea roșie, galbenă și albastră, deci în total 1818 litri de vopsea neagră

Log in or sign up to be able to send submissions!