Chọn ô

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

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

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ là số cột của bảng.
• Dòng thứ $i$ trong $4$ dòng tiếp theo chứa $n$ số nguyên $a_{i,1},a_{i,2},\dots ,a_{i,n}$ là các số trên dòng $i$ của bảng ($i=1,2,3,4$).

Hai số liên tiếp trên một dòng cách nhau ít nhất một dấu cách.

Dữ liệu ra

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

Ràng buộc

• $1\le n\le 10000$.
• $|a_{i,j}|\le 30000$.

Subtasks

• Subtask 1 ($50\%$ số test): $n\le 1000$.
• Subtask 2 ($50\%$ số test): $1000<n\le 10000$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ