Allergy Test#544
A test for allergy is conducted over the course of several days, consisting of exposing you to different substances (called allergens). The goal is to determine exactly which of the allergens you are allergic to. Each allergen has a live duration measured in whole days. This indicates exactly how many days you will suffer from an allergic reaction if you are sensitive to that allergen. An allergic reaction starts almost immediately after you have been exposed to an allergen that causes you allergies. The daily procedure includes:
I. At 8 o'clock each morning, at most one of the allergens is applied to your body.
II. At 8 o'clock each evening, you are examined for allergic reactions.
Thus, an allergen with live duration will affect exactly allergic reaction examinations.
If there are two or more active allergens in your body at the time of an observed reaction, you cannot determine which substance caused the allergy using only that information.
Your task is to find the shortest possible non-adaptive test scheme, given the durations of the allergens. Furthermore, the scheme must be fixed in advance and non-adaptive, meaning you may not choose which allergen to apply next depending on previous results.
The first line contains a single integer (1 \leq k \leq 20) specifying the number of allergens being tested for. The next lines each contain an integer (1 \leq d \leq 7), specifying the live duration of each allergen in full days.
Output the minimum number of days required for a non-adaptive scheme to conclusively test the allergens.
A scheme ends the morning when you no longer have active allergens in your body. For a single allergen with live duration , the scheme lasts days.
Example 1