스카이라인 Batch 컴파일 명령

여러분은 도시의 아름다운 스카이라인을 감상하고 싶습니다. 이를 위해 여러분은 $N$개의 고층 건물을 일렬로 건설하기로 했습니다. $i$번째 건물은 정확히 $h_{i}$층이어야 합니다.

여러분은 여러 개의 건설 회사에게 주문을 할 수 있습니다. 승현이의 회사는 1개의 고층 건물에 한 개의 층을 더 짓는 데 3백만원를 요구합니다. 지학이의 회사는 두 개의 인접한 고층 건물들에 한 개의 층을 더 짓는데 5백만원를 요구합니다. 두 건물의 층수가 달라도 층을 하나 더 올릴 수 있습니다. 석환이의 회사는 세 개의 연속적인 고층 건물들에 한 개의 층을 더 짓는 데 7백만원를 요구합니다.

여러분은 원하는 순서대로 층을 올릴 수 있습니다. 건설을 끝마치기 위해서 드는 최소한의 돈이 얼마인지 구합시다.

입력 형식

첫 번째 줄에 $N$이 주어집니다. ($1 \le N \le 300$) 두 번째 줄에 $h[1], h[2], \cdots, h[N]$ ($1 \le h[i] \le 200$)이 공백을 사이로 두고 주어집니다.

출력 형식

건설을 끝마치기 위해 지불해야 하는 돈을 100만원 단위로 출력합니다.

예제