Вам даны \(n\) палочек с длинами \(a_1, a_2, \ldots, a_n\). Найдите максимальное количество правильных (равносторонних) многоугольников, которые вы можете сформировать одновременно, чтобы:
- Каждая сторона многоугольника была образована ровно одной палочкой.
- Ни одна палочка не использовалась более чем в \(1\) многоугольнике.
Обращаем ваше внимание, что палочки нельзя ломать.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке одно целое число — максимальное количество правильных (равносторонних) многоугольников, которые вы можете сформировать одновременно из имеющихся палочек.
Примечание
В первом наборе входных данных есть только одна палочка, поэтому мы не можем сформировать ни одного многоугольника.
Во втором наборе входных данных двух палочек также недостаточно, чтобы сформировать многоугольник.
В третьем наборе входных данных мы можем использовать \(4\) палочки длины \(3\) для формирования квадрата.
В четвертом наборе входных данных мы можем сформировать пятиугольник со стороной длиной \(2\) и квадрат со стороной длиной \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1
2
1 1
6
2 2 3 3 3 3
9
4 2 2 2 2 4 2 4 4
|
0
0
1
2
|