Đường đi tổng lớn nhất

Cho một bảng hình chữ nhật gồm $3$ hàng và $n$ cột. Ô ở hàng $i$, cột $j$ chứa số nguyên $a_{ij}$. Từ một ô, bạn có thể di chuyển sang ô kề cạnh (chung cạnh) với nó.

Hãy tìm một đường đi từ ô trái trên (hàng $1$, cột $1$) đến ô phải dưới (hàng $3$, cột $n$) sao cho không ô nào được thăm quá một lần và tổng các số trên các ô thuộc đường đi là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: số cột của bảng.
• Ba dòng tiếp theo, mỗi dòng chứa $n$ số nguyên: số thứ $j$ của dòng thứ $i$ là giá trị $a_{ij}$.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng lớn nhất của các số trên một đường đi hợp lệ từ ô trái trên đến ô phải dưới.

Ràng buộc

• $1\le n\le {10}^5$
• $-{10}^9\le a_{ij}\le {10}^9$

Ví dụ