Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Một nửa ma trận vuông cấp n là một tam giác vuông cân, trên mỗi ô của tam giác có chứa một số nguyên.
Tại một ô của tam giác là (i,j), có thể đi đến 1 trong 3 ô là (i+1,j-1), (i+1,j) và (i+1,j+1). Có thể xem ở hình dưới:




 


(i,j)


 




i+1,j-1


i+1, j


i+1,j-1




Hãy tìm một hành trình từ đỉnh tam giác xuống đáy của tam giác sao cho tổng các ô trên hàng trình đi là lớn nhất.
Input:
- Dòng 1 chứa N (1 <= N <= 100)
- N dòng tiếp theo, dòng thứ i chứa i số nguyên
Output:
- Dòng 1 là số S: tổng giá trị lớn nhất trên hành trình
- N dòng tiếp theo, dòng thứ i chứa giá trị j tức là sẽ đi qua dòng i cột j trên hành trình.
Ví dụ




INPUT


OUTPUT


Giải   thích ví dụ




5
3
1 5
7 2 8
8 3 5 6
1 9 3 7 3


32
1
2
1
1
2


Các số được bôi đậm là các số   đi trên hành trình