(robotcq.*)

Cho lưới ô vuông gồm \(3\) hàng và \(N\) cột, ô ở hàng \(i\) và cột \(j\) được đặt một phần quà có giá trị \(A_{ij}\ (1 \leq i \leq 2,\ 1 \leq j \leq N,\ 1 \leq A_{ij} \leq 10^{9})\).

Một rô-bốt xuất phát từ ô \((1,1)\) và di chuyển đến ô \((3,N)\) theo quy tắc sau:

+ Nếu rô-bốt đang đứng ở ô \((i,j)\) thì có thể di chuyển đến ô \((i + 1,j)\) hoặc \((i,j + 1)\);

+ Rô-bốt không được di chuyển ra khỏi lưới ô vuông.

Với mỗi đi qua, rô rô-bốt nhận được phần quà đã được đặt sẵn tại ô đó.

Yêu cầu: Tính tổng giá trị các phần quà mà rô-bốt có thể nhận được lớn nhất là bao nhiều?

Dữ liệu vào:

+ Dòng đầu ghi số nguyên dương \(N\);

+ Dòng thứ hai ghi \(N\) số nguyên \(A_{11},A_{12},\ldots,A_{1N}\);

+ Dòng thứ ba ghi \(N\) số nguyên \(A_{21},A_{22},\ldots,A_{2N}\);

+ Dòng thứ tư ghi \(N\) số nguyên \(A_{31},A_{32},\ldots,A_{3N}\);

+ Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Kết quả:

+ Ghi một số nguyên duy nhất là tổng giá trị các phần quà lớn nhất mà rô-bốt có thể nhận được.

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm của bài thỏa mãn: \(1 \leq N \leq 500\);

• Có 30% số test tương ứng với 30% số điểm của bài thỏa mãn: \(1 \leq N \leq 5\ 000\);

• Có 40% số test tương ứng với 40% số điểm của bài thỏa mãn: \(5000 \leq N \leq 10^{6}\).

Ví dụ: