Cho một bảng hình chữ nhật kích thước ~5 \times n~ ô vuông. Các dòng được đánh số từ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến ~n~ từ trái qua phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i,j)~. Trên mỗi ô ~(i,j)~ có ghi một số nguyên ~A_{ij}~, ~i = 1, 2, 3, 4, 5~; ~j = 1, 2, \dots, n~. Một cách chọn ô là việc xác định một tập con khác rỗng ~S~ của tập tất cả các ô của bảng sao cho không có hai ô nào trong ~S~ có chung cạnh. Các ô trong tập ~S~ được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn.

Yêu cầu: Tìm cách chọn sao cho trọng lượng là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số cột của bảng.
• Cột thứ ~j~ trong số ~n~ cột tiếp theo chứa 5 số nguyên ~a_{1j}, a_{2j}, a_{3j}, a_{4j}, a_{5j}~, hai số liên tiếp cách nhau ít nhất một dấu cách, là 5 số trên cột ~j~ của bảng.

Output

• Gồm 1 dòng duy nhất là trọng lượng của cách chọn tìm được.

Sample Input 1

3
-1 9 3
-4 5 -6
7 8 9
9 7 2
9 4 9

Sample Output 1

50