Vopsea

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 $N$ găleți de vopsea deja amestecată. Vopseaua $i \ (1 ≤ i ≤ N )$ s-a obținut prin amestecarea a $r_i$ litri de vopsea rosșie, $g_i$ litri de vopsea galbenă și $a_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ă $N$ , numărul de galeți de vopsea.

Pe următoarele $N$ linii se vor găsi câte $3$ numere, pe linia $i$ găsindu-se numerele $r_i, g_i$ și $a_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

• $1 \leq N \leq 40$
• $0 \leq r_i, g_i, a_i \leq 10^6$
• Am notat $S = max\{\sum_{i=1}^{N}a_i, \sum_{i=1}^{N}r_i, \sum_{i=1}^{N}g_i\}$

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, 5$ și $6$, atunci vom avea câte $6$ litri de vopsea roșie, galbenă și albastră, deci în total $18$ litri de vopsea neagră