Đề bài

Ngày nay, các nhà khoa học đã nghĩ ra một trò chơi trên ma trận rất thú vị. Thông qua trò chơi này có thể đo IQ một cách khá hiệu quả.

Trò chơi được mô tả như sau:

Bạn có một ma trận A kích thước 8 × N, trên đó gồm các số nguyên là điểm của các ô. Người chơi sẽ được yêu cầu chọn một tập khác rỗng các ô trên ma trận này, sau đó tính tổng điểm trên những ô đã chọn.

Điều kiện: Trong những ô được chọn không có hai ô nào kề cạnh (kề cạnh nghĩa là chung một cạnh).

IQ của người chơi sẽ tỉ lệ thuận với tổng điểm nhận được.

Tony tham gia trò chơi và đạt kết quả khá tốt. Bây giờ Sherry muốn biết tổng điểm lớn nhất có thể nhận được trong trò chơi này là bao nhiêu. Bạn hãy giúp Tony nhé!

Input

Dòng đầu tiên là số nguyên N( 1 ≤ N ≤ 10000).
8 dòng tiếp theo: Mỗi dòng chứa N số nguyên, số nguyên ở hàng i cột j là a_i,j,( | a_i,j | ≤ 10^8).

Output

Gồm 1 dòng duy nhất là số điểm lớn nhất tìm được.

Sample input

2
-22 2
-33 45
56 -60
-8 -38
79 66
-10 -23
99 46
1 -55

Sample output

279

NOTE

Chọn các ô (3,1) (5,1) (7,1) (2,2).