Nếu không thấy được đề bài. Hãy đọc tại đây.
Trong một giờ giải lao tại Trại hè Sáng tạo Khoa học, thầy giáo tổ chức cho các bạn học sinh một trò chơi trên lưới lục giác kích thước \(N\). Biết rằng, một lưới lục giác kích thước \(N\) là một lưới gồm \(2N - 1\) hàng; mỗi hàng có một số ô; mỗi ô trên đó được viết một số nguyên. Ví dụ, đây là một lưới lục giác kích thước \(3\):

Các bạn học sinh được điều khiển một robot, ban đầu xuất phát tại một ô bất kỳ nằm ở hàng đầu tiên. Trong mỗi lượt đi, robot có thể di chuyển xuống một ô nằm ở hàng ngay bên dưới và có chung cạnh với ô hiện tại. Trong các ô có thể đi tới, ô nằm lệch về phía bên trái được gọi là đi xuống trái, còn ô nằm lệch về phía bên phải được gọi là đi xuống phải. Trò chơi kết thúc khi robot đi đến hàng cuối cùng.

Để tạo thử thách cho các bạn, thầy hướng dẫn yêu cầu robot không được đi xuống trái hoặc đi xuống phải ba lần liên tiếp và tổng các số được ghi trên các ô đã đi qua là lớn nhất có thể.

Yêu cầu

Hãy xác định tổng các số trên các ô đã đi qua lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) là kích thước của lưới lục giác mà thầy giáo tổ chức trò chơi (\(1 \le N \le 1067\)).
• \(2N - 1\) dòng tiếp theo, dòng thứ \(i\) chứa các số nguyên không âm được viết trên các ô thuộc hàng thứ \(i\) theo thứ tự từ trái qua phải.
• Dữ liệu đảm bảo các số được viết trên lưới không vượt quá \(10^9\).

Output

• Ghi ra một số nguyên duy nhất là kết quả của bài toán.

Example

3
1 2 3
3 2 2 1
8 9 10 11 12
13 14 15 16
17 18 19

51

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 8\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.