정수 삼각형

삼각형 모양으로 정수가 배열되어 있다. 꼭대기에서 출발하여 매 단계마다 아래 행의 인접한 두 수 중 하나를 골라 내려갈 때, 지나는 수들의 합의 최댓값을 구하라. ## 입력 첫째 줄에 삼각형의 크기 N이 주어진다. 둘째 줄부터 N+1번째 줄까지 삼각형의 각 행이 주어진다. i번째 행에는 i개의 수가 있다. - 1 ≤ N ≤ 500 - 0 ≤ 각 수 ≤ 9,999 ## 출력 꼭대기에서 바닥까지 이동하며 얻을 수 있는 최대 합을 출력한다. ## 예제 입력 1 ``` 4 1 2 3 4 5 6 7 8 9 10 ``` ## 예제 출력 1 ``` 20 ```