10042 계단 오르기 Silver III

문제

계단은 한 번에 1칸 또는 2칸을 오를 수 있다. 단, 연속으로 3칸을 밟을 수 없다. 시작점은 계단이 아니며, 마지막 계단은 반드시 밟아야 한다.

각 계단에는 점수가 있을 때, 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 계단의 수 N (1 ≤ N ≤ 300)이 주어진다. 둘째 줄에 각 계단의 점수가 공백으로 구분되어 주어진다. 각 점수는 1 이상 10,000 이하이다.

출력

얻을 수 있는 최대 점수를 출력한다.

6
10 20 15 25 10 20

75