Cho một bảng hình chữ nhật kích thước 5×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 Aij , i =1, 2, 3, 4, 5; j =1, 2, ..., 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.

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

Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây:

Cách chọn cần tìm là tập các ô S = {(3,1),(4,1),(5,1) (1,2),(2,2),(3,3) (3,4), (3,5)} với trọng lượng 50.

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 a1j, a2j, a3j, a4j, a5j 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.

Hạn chế

Trong tất cả các test: n ≤ 10000, |aij| ≤ 30000. Có 50% số lượng test với n ≤ 1000.