체리모야

Farah는 이국적인 체리모야 과일을 매우 좋아한다. 이 과일은 먼 나라에서 오기 때문에 스웨덴에서는 일 년에 단 하루만 판매된다! 물론 Farah는 바로 이날을 놓치지 않고 체리모야를 몇 개 샀다.

체리모야의 익은 정도는 서로 다르다. 일부는 바로 그날 막 익었지만, 일부는 나중에 먹기 좋게 익는다.

더 정확히 말하면, 각 체리모야 과일은 총 3일 동안 먹기 좋게 익은 상태이다. 우리는 그 과일이 먹기 좋게 익기 시작한 날을 과일이 익은 날이라고 한다. 그전에는 먹을 수 없고, 그 사흘이 지나면 버려야 한다.

Farah는 체리모야 철을 최대한 활용하고 싶다. 그녀는 즐거움을 최대화하려 하며, 즐거움은 다음과 같이 계산한다. 주어진 하루에 첫 번째 체리모야에서는 10 즐거움 점수를 받고, 두 번째에서는 9, 세 번째에서는 8을 받는 식이다. 그녀는 하루에 절대로 체리모야를 10개보다 많이 먹을 수 없다.

매일 먹기 좋게 익는 체리모야의 수가 주어질 때, Farah가 그해 체리모야 철에 얻을 즐거움 점수를 구하는 프로그램을 작성하라.

점수 산정

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $20$ | $N \leq 1$

$2$ | $20$ | $N \leq 2$

$3$ | $30$ | $N \leq 5$

$4$ | $30$ | 추가 제한 없음.

입력의 첫 번째 줄에는 체리모야가 익을 수 있는 날의 수를 나타내는 정수 $N$ ($1 \leq N \leq 15$)이 주어진다.

이어지는 $N$일 각각에 대해 정수 $C_i$ ($0 \leq C_i \leq 30$)이 주어지며, 이는 그날 체리모야 $C_i$개가 익는다는 뜻이다. 따라서 체리모야를 먹는 것이 가능한 기간은 $N+2$일이다.

최적의 섭취 전략으로 Farah가 얻을 수 있는 즐거움 점수의 최댓값을 정수 하나로 출력한다.

최적 전략은 다음과 같다.

• 1일에 익는 체리모야 18개 중에서 1, 2, 3일에 6개씩 먹는다. 그러면 각 날에 $10+9+8+7+6+5=45$의 즐거움 점수를 얻는다.

• 2일에 익는 체리모야 2개 중에서 4일에 하나, 5일에 하나를 먹는다. 그러면 각 날에 $10$의 즐거움 점수를 얻는다.

• 이를 모두 합하면 즐거움 점수 $45*3+10*2=155$점을 얻는다. 이보다 더 많은 즐거움 점수를 얻는 전략은 없다.