휴식이 필요해 timer 1s memory 64MB

여러분은 정올 캠프에 참가하여 모의고사를 치르고 있다.

모의고사에는 N개의 문제가 있는데, 각 문제 별로 해결하는데 필요한 시간이 다르다.

i번째 문제를 푼다고 하면, d_i초가 걸린다.

하지만 문제를 연속으로 푸는 것은 너무 힘든 일이다. 만약 문제를 연속으로 푼다고 한다면, 해결하는데 걸리는 시간이 2배씩 증가한다.

1, 2, 3번 문제를 연속으로 해결한다고 가정하면, 첫 문제는 d_1초 만에 해결할 수 있지만 두 번째 문제는 2 × d_2초 만큼 걸리며, 세 번째 문제는 4 × d_3초 만큼 걸린다.

만약 그 상태에서 문제를 하나 더 해결한다면 원래의 8배의 시간이 걸릴 것이다.

그러니 때때로 조금 쉬는 것이 문제를 더 잘 해결할 수 있을 수도 있다. 여러분이 1시간(3600초)을 쉰다면, 여러분은 기운을 완전히 회복하여 다시 원래의 시간으로 문제를 해결할 수 있다.

문제를 푸는 순서는 자유롭게 바꿀 수 있으며, 한 번 풀기 시작한 문제는 끝까지 풀어야 한다.

문제의 순서와 휴식을 적절히 배치하여 모든 문제를 해결하는데 걸리는 최소 시간을 알아내자!