Đề bài

Cho một bảng hình chữ nhật kích thước 4 × n (4×n ô vuông).
Các hàng được đánh số i = 1, 2, 3, 4 và các cột được đánh số 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 ô trong 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, và tổng các số trong các ô được chọn được gọi là tổng của cách chọn.

Hãy tìm cách chọn sao cho tổng là lớn nhất.

Input

• Dòng đầu tiên: số nguyên dương n – số cột của bảng.
• n cột tiếp theo: mỗi cột gồm 4 số nguyên a_1,j, a_2,j, a_3,j, a_4,j – giá trị trên các ô của cột j.
• Hai số liên tiếp cách nhau ít nhất một dấu cách.

Output

• Gồm 1 dòng duy nhất – tổng lớn nhất có thể tìm được.

Giới hạn

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

Ví dụ

Input

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

Output

32

Giải thích

Với n = 3, bảng được biểu diễn như sau:

Cách chọn tối ưu có thể là: S = {(3,1), (1,2), (4,2), (3,3)} với tổng = 32.