허프만 되돌리기

정적 허프만 부호화는 주로 텍스트 압축에 쓰는 부호화 알고리즘이다. 서로 다른 문자 $N$개로 이루어진 텍스트가 주어지면, 알고리즘은 문자마다 부호를 하나씩 정해 $N$개의 부호를 고르고 그 부호로 텍스트를 압축한다. 부호를 고르려고 알고리즘은 잎이 $N$개인 이진 루트 트리를 만든다. $N \ge 2$인 경우 트리는 다음 순서로 만든다.

1. 텍스트에 나오는 서로 다른 문자마다 노드가 하나뿐인 트리를 만들고, 그 문자가 텍스트에 나온 횟수를 가중치로 삼는다.
2. 위에서 만든 트리 $N$개를 담은 집합 $s$를 만든다.
3. $s$에 트리가 둘 이상 있는 동안 다음을 반복한다.
   1. 가중치가 가장 작은 트리 $t_1 \in s$를 골라 $s$에서 뺀다.
   2. 가중치가 가장 작은 트리 $t_2 \in s$를 골라 $s$에서 뺀다.
   3. $t_1$을 왼쪽 서브트리, $t_2$를 오른쪽 서브트리로 하는 새 트리 $t$를 만들고, $t_1$과 $t_2$의 가중치 합을 $t$의 가중치로 삼는다.
   4. $t$를 $s$에 넣는다.
4. $s$에 남은 하나뿐인 트리를 반환한다.

3의 1번과 2번 단계에서 가중치가 가장 작은 트리가 여러 개일 수 있으므로, 텍스트가 같아도 트리 모양은 하나로 정해지지 않는다. 텍스트 abracadabra에서 a는 5번, b와 r은 각각 2번, c와 d는 각각 1번 나온다. 어떤 실행은 a, b, r, c, d의 부호 길이를 1, 2, 3, 4, 4로 만들고, 다른 실행은 1, 3, 3, 3, 3으로 만든다.

문자의 부호는 완성된 트리에서 루트부터 그 문자에 해당하는 잎까지 가는 경로로 정해진다. 부호의 길이는 그 경로에 있는 간선의 수이고, 경로에 있는 내부 노드의 수와 같다.

알고리즘이 고른 부호 $N$개의 길이가 주어진다. 만들어진 부호의 길이가 정확히 그 길이가 되게 하는 텍스트 중에서 가장 작은 크기, 즉 전체 문자 수의 최솟값을 구하라.

첫째 줄에 텍스트에 나오는 서로 다른 문자의 수를 뜻하는 정수 $N$이 주어진다. ($2 \le N \le 50$)

둘째 줄에 알고리즘이 각 문자에 고른 부호의 길이 $L_i$가 $N$개 주어진다. ($1 \le L_i \le 50$, $i = 1, 2, \dots, N$)

위에서 설명한 방법으로 만들 수 있는 트리 중에서 주어진 길이의 부호를 만드는 트리가 적어도 하나 있다.

만들어진 부호의 길이가 주어진 길이가 되게 하는 텍스트의 가장 작은 크기, 즉 전체 문자 수의 최솟값을 정수 하나로 한 줄에 출력한다.