Xét tam giác số bên dưới. Viết chương trình tính tổng lớn nhất của các số trên đường đi bắt đầu ở đỉnh và kết thúc tại một vị trí bất kỳ trên đáy. Mỗi bước đi chéo xuống trái hoặc xuống phải.

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

Trong ví dụ, đường đi qua 7, 3, 8, 7, 5 cho tổng lớn nhất: 30.

Dữ liệu vào

Dòng đầu chứa số hàng $R$ ($1 \le R \le 1000$). Mỗi dòng tiếp theo chứa các số nguyên của hàng tương ứng trong tam giác. Tất cả không âm và không lớn hơn 100.

Dữ liệu ra

Một dòng chứa tổng lớn nhất theo cách di chuyển đã nêu.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

30