Time Limit: 1s
Memory Limit: 128MB
소들은 볼링을 칠 때 실제 볼링 핀을 사용하지 않습니다. 그들은 대신 0~99까지의 숫자를 하나 가지고 볼링 핀 배열과 같은 삼각형의 형태를 취합니다. 예를 들면.. 아래처럼 말이죠
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
볼링 공 역할을 수행하는 소는 삼각형의 꼭대기에서 부터 아래 방향으로 좌측 혹은 우측 소를 선택하면서 가장 아래까지 이동합니다. 볼링 공 소의 점수는 이동하면서 거친 볼링 핀 소가 가지고 있는 점수의 합입니다. 가장 높은 점수를 가진 소가 우승하게 됩니다.
N(1~350) 줄의 삼각형이 주어졌을 때, 획득 가능한 가장 큰 점수는 몇점일까요?
* Line 1 : 단일 정수 N (삼각형이 가지는 줄-row-의 수)
* Line 2 ~ N+1 : (라인 번호 - 1)개의 정수
* Line 1 : 이동 과정에서 얻을 수 있는 최고 점수
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
30
샘플에 대해 가장 높은 점수를 획득할 수 있는 이동 경로는 아래와 같습니다. *가 각 과정에서 선택한 이동 경로입니다.
7
*
3 8
*
8 1 0
*
2 7 4 4
*
4 5 2 6 5