Bài toán tìm tổng lớn nhất trong tam giac

Cho ma trận A hình vuông có kích thước n*n. Đầu tiên bạn ở ô có tọa độ [1,1], bạn được phép đi sang phải và đi xuống dưới ô kề cạnh. Hãy tìm đường đi có tổng lớn nhất khi đi đến ô [n,n].

Input

-Dòng đầu là số nguyên dương N [n