Hình trên cho một tam giác số. Từ đỉnh xuống đáy của tam giác có rất nhiều đường đi khác nhau. Với mỗi đường đi, cộng các số nằm trên đường đi đó lại ta được một tổng; nhiệm vụ của bạn là tìm tổng lớn nhất.

Mỗi bước trên đường đi chỉ được đi từ một số xuống số gần nhất bên trái hoặc số gần nhất bên phải của nó ở hàng dưới. Ngoài ra, số lần đi xuống bên trái và số lần đi xuống bên phải không được chênh lệch nhau quá 1.

Dữ liệu vào

Dòng đầu tiên của input gồm một số nguyên $N (1≤N≤100)$, là số hàng của tam giác.

$N$ dòng tiếp theo cho tam giác số. Các số trên tam giác đều là số nguyên từ $0$ đến $100$.

Dữ liệu ra

In ra một số nguyên, là đáp án.

Ví dụ

Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Output

27