Problem description

Dana jest prostokątna kratka wymiaru 4 × N wypełniona liczbami. Należy wybrać liczby o jak największej sumie, nie wolno jednak wybrać dwóch leżących w sąsiednich komórkach prostokąta. Dwie komórki prostokąta uznajemy za sąsiednie jeśli dzielą bok (a więc komórka może mieć co najwyżej czterech sąsiadów, a co najmniej dwóch).

Napisz program, który: wczyta wymiary prostokąta oraz umieszczone w nim liczby, wyznaczy maksymalną możliwą sumę liczb, które można wybrać zgodnie z zasadami i wypisze wynik na wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca szerokość prostokąta. W kolejnych czterech wierszach znajduje się po N liczb A_i, j. Są to liczby umieszczone w prostokącie.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć maksymalna suma liczb, które można wybrać zgodnie z regułami podanymi powyżej.

Ograniczenia

1 ≤ N ≤ 200 000, 0 ≤ A_i, j ≤ 10⁹.

W testach wartych łącznie 20% maksymalnej punktacji: N ≤ 10.

Przykład

5
5 2 5 1 4
1 5 3 10 3
0 0 4 1 4
0 0 8 1 1

41