Mô Tả Bài Toán:

Hình trên biểu diễn tam giác số.

Hãy viết chương trình tính tổng lớn nhất các số trên con đường bắt đầu từ đỉnh và kết thúc ở đáy thoả mãn yêu cầu đường đi như sau: Mỗi bước có thể đi chéo xuống phía trái hoặc đi chéo xuống phía phải.

• Dòng đầu tiên chứa số nguyên dương N, là số lượng dòng của tam giác số (Số lượng dòng trong tam giác lớn hơn 1 nhưng bé hơn 100).
• N dòng tiếp theo là các số trong tam giác đều là số nguyên từ 0 đến 99.

Dữ Liệu Vào:

• Dòng đầu tiên chứa một số nguyên N (2 ≤ N < 100), là số lượng dòng trong tam giác.
• N dòng tiếp theo, mỗi dòng chứa các số nguyên, với dòng thứ i chứa i số nguyên, đại diện cho các phần tử trong tam giác.

Dữ Liệu Ra:

• In ra tổng lớn nhất có thể đạt được từ đỉnh tam giác đến đáy tam giác.

Ví Dụ:

Dữ Liệu Vào:

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

Kết Quả:

30

Giải thích: Để tìm tổng lớn nhất, bạn cần bắt đầu từ đỉnh tam giác, sau đó tại mỗi bước, bạn có thể đi chéo xuống phía trái hoặc đi chéo xuống phía phải. Tổng lớn nhất trong ví dụ này là 7 -> 8 -> 8 -> 7 -> 5, kết quả là 30.