7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Hình trên là một bảng tam giác các số nguyên không âm. Hãy viết chương trình để tính tổng lớn nhất các số trên đường đi từ đỉnh tam giác và kết thúc tại một điểm nào đó ở đáy tam giác.

Mỗi nước đi ta được quyền đi thẳng xuống số phía dưới hoặc số bên phải của số ngay dưới nó (mỗi lần chỉ đi đến một số).

Dữ liệu input

+ Dòng 1: ghi số N là số lượng dòng của tam giác.

+ Dòng thứ i+1 (1<= i <= N) ghi i số nguyên không âm.

Kết quả :

+ Dòng 1: tổng lớn nhất đó.

        + Dòng 2: đường đi sao cho tổng tìm được là lớn nhất (gồm N số nguyên, mỗi số cách nhau một khoảng trắng).