PKU 1163. The Triangle

The Triangle

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 13569		Accepted: 7789

Description

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5



(Figure 1)

Figure 1은 숫자로 이루어진 삼각형입니다. 맨 위에서 시작해서 맨 아래의 한 지점에서 끝나는 임의의 길을 지나는 숫자들의 합들 중 가장 큰 것을 계산하는 프로그램을 만드세요. 각 스텝에서는 왼쪽아래 또는 오른쪽아래로 갈 수 있습니다.

Input

당신의 프로그램은 표준 입력으로 읽어들입니다. 첫째 줄은 하나의 정수 N을 포함하는데, 이것은 삼각형의 행의 개수를 의미합니다. 그 뒤의 N개 줄은 삼각형의 데이터를 서술합니다. 삼각형의 행의 개수는 1보다는 크고 100보다는 작거나 같습니다. 삼각형 안의 숫자들은 모두 정수이며, 0보다 크거나 같고 99보다 작거나 같습니다.

Output

당신의 프로그램은 표준 출력으로 써내려갑니다. 정수로 된 합들 중 가장 큰 것을.

Sample Input

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

Sample Output

30

Source

IOI 1994

*역자 주

1. 약간 졸립기도 하고, 영어가 부족한 것도 있고 해서 번역이 깔끔하지 못할 것입니다 =_= 고칠만한 부분은 댓글로 달아주세요//

2. 예시에 나온 삼각형은 7, 3, 8, 7, 5 순서로 타고 내려가면 그 합이 30이 되고, 다른 어떤 길 위의 합도 30보다 크지 않습니다