Một đoàn khảo cổ trong chuyến thám hiểm sa mạc đã phát hiện một kim tự tháp cổ xây bằng những phiến đá xếp thành nhiều tầng. Tầng thứ \(i\) có đúng \(i\) phiến đá xếp liền nhau, mỗi phiến được khắc một số nguyên (có thể âm, có thể dương). Một du khách dũng cảm bắt đầu hành trình từ phiến đá duy nhất ở đỉnh kim tự tháp (tầng 1). Mỗi bước, du khách được chọn đi xuống phiến đá phía dưới bên trái hoặc phía dưới bên phải của phiến đang đứng. Hành trình kết thúc khi chạm tầng cuối cùng.

Du khách muốn thu thập tổng các số trên những phiến đá đã đi qua là lớn nhất có thể. Hãy giúp du khách chọn đường đi tốt nhất.

Định dạng đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 2000\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa đúng \(i\) số nguyên (\(-10^9 \le \text{giá trị} \le 10^9\)).

Định dạng đầu ra

• In ra tổng lớn nhất có thể thu thập được trên đường đi.

Ví dụ

Input:

4
1
2 3
4 -1 2
3 2 5 1

Output:

11

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 10\).
• \(30\%\) số điểm ứng với \(N \le 200\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.