Тест на алергію
Тест на алергію проводиться протягом кількох днів, під час яких вас піддають впливу різних речовин, відомих як алергени. Мета тесту — визначити, які саме алергени викликають у вас реакцію. Кожен алерген має тривалість дії d, що вимірюється в повних днях. Це означає, що протягом цього часу ви будете відчувати алергічну реакцію, якщо у вас є схильність до цього алергену. Реакція починається одразу після введення алергену, якщо ви до нього чутливі. Щодня виконуються такі дії:
I. О 8 годині ранку у ваш організм вводиться не більше одного алергену.
II. О 8 годині вечора вас обстежують на наявність алергічних реакцій.
Алерген з тривалістю дії d викликатиме реакцію протягом d обстежень.
Якщо у вашому організмі одночасно присутні два або більше алергенів, то під час обстеження, маючи лише цю інформацію, ви не зможете визначити, яка саме речовина викликала алергію.
Вам потрібно знайти найкоротшу схему тестування, знаючи тривалість дії кожного алергену. Крім того, ваша схема повинна бути універсальною, тобто не адаптивною, а фіксованою для майбутнього використання. Це означає, що ви не можете обирати, який алерген вводити наступним, залежно від попередніх результатів.
Вхідні дані
Перший рядок містить кількість алергенів k (1 ≤ k ≤ 20), на які вас будуть перевіряти. Кожен з наступних k рядків містить тривалість d (1 ≤ d ≤ 7) дії алергену (в повних днях).
Вихідні дані
Виведіть найменшу кількість днів, протягом яких слід провести неадаптивну схему тестування алергенів.
Схема закінчується вранці, коли у вашому організмі вже не залишилося активних алергенів. Схема тестування для одного алергену з тривалістю дії d триває d днів.