28085번 - 배 옮기기 (Hard)

문제

치훈이는 배 \(N\)척을 강 건너편으로 옮기려고 한다. 강을 건너가거나 건너오기 위해서는 치훈이가 가지고 있는 배를 운전하여 건너야 한다.

배의 크기가 \(X\)라고 할 때, 치훈이가 그 배를 운전하여 강 건너편으로 옮기는 데에는 \(X\)분이 걸린다.

배를 운전하여 옮길 때, 크기가 더 작은 배를 최대 한 척까지 싣고 동시에 옮기는 것도 가능하다. 이 때 배를 옮기는 시간은 큰 배 하나를 옮기는 것과 같은 시간이 걸린다.

이 때, 치훈이가 배 \(N\)척을 모두 강 건너편으로 옮기는데 필요한 최소 시간을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 배의 개수 \(N\)이 주어진다.

둘째 줄에 \(i\)번째 배의 크기를 나타내는 \(B_i\)가 공백으로 구분되어 주어진다.

출력

치훈이가 모든 배를 강 건너편으로 옮기는데 필요한 최소 시간 (분)을 출력한다.

만약 어떤 방법을 써도 모든 배를 강 건너편으로 옮길 수 없다면 -1을 출력한다.

제한

• 1ドル ≤ N ≤ 100$
• 1ドル ≤ B_i ≤ 100,000円$
• $B_i$ 는 정수이다.

힌트

1번 예제에서 배를 옮기는 방법은 다음과 같다. 치훈이가 운전하고 있는 배는 흰색으로 표시하였다.