메뉴 건너뛰기

문제

00b18 음료수 0  

시간메모리제출 올바른 답 비율
1초64MB
176
48
27.3%


나의 횟수나의 최근 판정시도 성공 비율
6339
61.9%
음료수  

한 음료수 회사에서 시식회를 열었다. 그 곳에 갔더니, 테이블 위에 음료수가 일렬로 놓여 있었다. 여기에는 다음과 같은 두 가지 규칙이 있다.

  1. 음료수를 선택하면 그 잔에 들어있는 음료수는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

1부터 n까지의 번호가 붙어 있는 n개의 음료수가 순서대로 테이블 위에 놓여 있고, 각 음료수의 양이 주어졌을 때, 가장 많은 양의 음료수를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 음료수 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 음료수가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 음료수 잔을 선택하면 총 음료수 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 음료수의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 음료수 잔에 들어있는 음료수의 양이 순서대로 주어진다. 음료수의 양은 1,000 이하의 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 음료수의 양을 출력한다.

예시
1입력
6
6
10
13
9
8
1
출력
33
위로