알레르기 검사

알레르기 검사는 여러 날에 걸쳐 진행됩니다. 매일 여러분은 알레르겐(allergen) 이라 불리는 물질에 노출될 수 있으며, 목표는 여러분이 정확히 어떤 알레르겐에 알레르기가 있는지 알아내는 것입니다.

각 알레르겐에는 정수 일 단위의 지속 기간 $D$가 있습니다. 어떤 알레르겐에 알레르기가 있다면, 그 알레르겐에 노출된 직후부터 정확히 $D$일 동안 알레르기 반응이 나타납니다.

하루에는 정해진 행동 시점이 두 번 있습니다.

• I. 매일 아침 8시에, 최대 한 개의 알레르겐을 몸에 노출시킵니다.
• II. 매일 저녁 8시에, 알레르기 반응이 있는지 검사합니다.

따라서 지속 기간이 $D$인 알레르겐은 정확히 $D$번의 저녁 검사에 영향을 줍니다.

어떤 반응이 관찰된 시점에 몸속에서 두 개 이상의 알레르겐이 활성 상태라면, 그 관찰 결과만으로는 그중 어떤 물질에 알레르기가 있는지 구별할 수 없습니다.

주어진 알레르겐들의 지속 기간에 대해, 가능한 한 가장 짧은 검사 계획을 세우려고 합니다. 이 계획은 비적응적(non-adaptive) 이어야 합니다. 즉, 계획은 미리 고정되어야 하며, 이전 검사 결과에 따라 알레르겐을 언제 노출시킬지 바꿀 수 없습니다. 확실하게 판별할 수 있는 계획에 필요한 최소 일수를 구하세요.

첫 번째 줄에는 검사할 알레르겐의 개수를 나타내는 정수 $k$ ($1 \le k \le 20$)가 주어집니다. 이어지는 $k$개의 줄에는 각 알레르겐의 지속 기간을 나타내는 정수 $D$ ($1 \le D \le 7$)가 한 줄에 하나씩 주어집니다.

확실하게 판별할 수 있는 가장 짧은 비적응적 검사 계획의 일수를 출력합니다.

검사 계획은 몸속에 활성 알레르겐이 더 이상 남아 있지 않게 되는 날 아침에 끝납니다. 따라서 지속 기간이 $D$인 알레르겐 하나를 검사하는 계획은 $D$일이 걸립니다.