문제 설명
세종이는 프로그래밍 경진대회 이벤트로 또 다른 보물 찾기를 준비하였다. 예를 들어 깊이가 \(3\)인 보물 지도는 아래와 같이 마지막 깊이를 제외하고 각 보물이 있는 지점에서부터 다음 깊이에 \(2\)개씩의 지점으로 연결되어 있다. 대회에 참가한 학생은 깊이\(1\)에서 시작하여 깊이\(3\)으로 연결된 길을 따라 이동할 수 있다.
깊이가 \(3\)인 보물 지도의 각 지점에 숨겨진 보물의 양이 왼쪽과 같을 때, 획득할 수 있는 최대 보물의 양은 오른쪽 그림과 같이 \(7\)개이다.
보물 지도가 주어질 때, 획득할 수 있는 보물의 양의 최댓값을 출력하는 프로그램을 작성하시오.
깊이가 \(3\)인 보물 지도의 각 지점에 숨겨진 보물의 양이 왼쪽과 같을 때, 획득할 수 있는 최대 보물의 양은 오른쪽 그림과 같이 \(7\)개이다.
보물 지도가 주어질 때, 획득할 수 있는 보물의 양의 최댓값을 출력하는 프로그램을 작성하시오.
입력 설명
첫 번째 줄에는 보물 지도의 깊이 \(n\)이 입력된다.
두 번째 줄에는 각각의 지점에 숨겨져 있는 보물의 양(\(a_i\))이 공백을 기준으로 입력된다.
\((1 \le n \le 20, 1 \le a_i \le 100)\)
단, 깊이 \(1\)에서의 보물이 있는 지점은 \(1\)곳이며, 각 깊이마다 \(2\)배씩 늘어난다.
두 번째 줄에는 각각의 지점에 숨겨져 있는 보물의 양(\(a_i\))이 공백을 기준으로 입력된다.
\((1 \le n \le 20, 1 \le a_i \le 100)\)
단, 깊이 \(1\)에서의 보물이 있는 지점은 \(1\)곳이며, 각 깊이마다 \(2\)배씩 늘어난다.
출력 설명
획득할 수 있는 보물의 최댓값을 출력한다.
입력 예시 Copy
3
1 2 3 3 4 1 2
출력 예시 Copy
7