계단 오르기 1

문제

서현이는 $N$개로 이루어진 계단을 올라야 한다. 각 계단에는 정수가 적혀있는데, 해당 계단을 밟으면 그 만큼의 점수를 얻는다. 서현이는 다음 규칙을 만족하며 계단을 오르려고 한다.

• 한 번에 두 계단씩 혹은 세 계단씩 오를 수 있다.
• 마지막 계단은 반드시 밟아야 한다.

예를 들어 $N=9$이고 각 계단에는 순서대로 $[20, 10, 5, 30, 2, 5, 10, 1, 1]$이 적혀있다고 가정하자. 시작 지점에서부터 두 계단씩, 세 계단씩, 두 계단씩, 두 계단씩 오르게 되면 $[10, 2, 10, 1]$이 적힌 계단을 밟게 되고 이 경우에는 $23$점을 얻는다. 하지만 시작 지점에서부터 두 계단씩, 두 계단씩, 세 계단씩, 두 계단씩 오르게 되면 $[10, 30, 10, 1]$이 적힌 계단을 밟게 되고 이 경우에는 $51$점을 얻는다.

각 계단에 적힌 정수들이 주어질 때, 얻을 수 있는 최대 점수를 구해보자.

입력

첫째 줄에 $N$이 주어진다. ($2\le N\le 1\,000$)

둘째 줄에 $N$개의 계단에 적힌 정수 $A_i$가 순서대로 공백으로 구분되어 주어진다. ($0\le A_i\le 1\,000\,000$)

출력

서현이가 얻을 수 있는 최대 점수를 출력한다.

예제 입력 1

9
20 10 5 30 2 5 10 1 1

예제 출력 1

51