Gigel participă la un concurs de informatică împreună cu echipa sa. Echipa sa este formată din n membri. Concursul este împărțit în mai multe nivele, numerotate de la 1 la n. După completarea primului nivel, următorul va fi disponibil și așa mai departe.

Cerința

Știind eficiența cu care un membru al echipei poate rezolva un anumit nivel și faptul ca odată ce un membru al echipei lui Gigel a rezolvat un nivel, acesta nu mai poate contribui, să se afle eficiența maximă posibilă obținută de echipă.

Date de intrare

Fișierul de intrare teamwork.in conține pe prima linie numărul n. Pe linia i + 1 a fișierului se vor afla n numere, al j -lea număr reprezintă eficiența cu care membrul j poate rezolva nivelul i.

Date de ieșire

Fișierul de ieșire teamwork.out va conține pe prima linie numărul EMax, eficiența maximă pe care echipa lui Gigel o poate obține până la finalul concursului.

Restricții și precizări

• 1 ≤ n ≤ 18
• 1 ≤ eficiența ≤ 100
• eficiența echipei este egală cu suma eficiențelor cu care este rezolvat fiecare nivel
• toată lumea știe că echipa lui Gigel nu este lacomă

Exemplu:

teamwork.in

3
1 1 2
1 2 1
2 1 1

teamwork.out

6

Explicație

Primul nivel este rezolvat de al 3-lea membru.
Al doilea nivel este rezolvat de al 2-lea membru.
Ultimul nivel este rezolvat de primul membru.
2 + 2 + 2 = 6