408276: GYM103075 I Рудольф и M&M's

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Рудольф и M&M'sограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

У Байера сегодня день рождения. Рудольф решил порадовать своего питомца и купил ему его любимые конфетки M&M's. Байер очень обрадовался такому подарку, сразу же открыл пачку и высыпал разноцветные конфетки на стол.

Рудольф заметил, что в пачке были конфетки N различных цветов, причём, судя по всему, на кондитерской фабрике их насыпали в пачку автоматически: среди количеств конфет каждого цвета было не более шести различных.

Налюбовавшись на конфетки, Байер собрался съесть их все с чаем. Байер ест M&M's очень интересным способом: он выбирает интересную группу конфеток, съедает её и запивает одним глотком чая. Группа конфеток считается интересной, если количество конфеток каждого цвета в ней одинаково. Например, три красные и три синие конфетки формируют интересную группу, две синие, две зелёные и две жёлтые — тоже, а одна жёлтая и две красные — нет.

Рудольфу стало интересно, какое минимальное количество глотков чая потребуется Байеру, чтобы съесть и запить все конфетки. Помогите ему найти ответ на этот вопрос.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 105) — количество цветов конфеток.

Вторая строка содержит N целых чисел Ci (1 ≤ Ci ≤ 105) — количество конфеток каждого цвета в пачке. Среди чисел Ci количество различных не превосходит 6.

Выходные данные

Выведите одно целое число — минимальное количество глотков чая, которое потребуется Байеру, чтобы съесть все конфетки.

ПримерыВходные данные
3
3 10 2
Выходные данные
3
Входные данные
3
3 3 3
Выходные данные
1

加入题单

算法标签: