Районная олимпиада по информатике 2023 года за 9 класс | Казахстанские олимпиады

Задача C. Без переноса

Маленький Дамир еще не научился делать переносы при сложении чисел. Но он отлично справляется со сложением чисел, где не нужно делать перенос. Например, Дамир не сможет посчитать 27+5, но легко посчитает 31421+6374+3.

У вас есть $N$ чисел. Вам нужно среди них выбрать максимальное количество чисел, которых можно сложить без переноса.

Формат входного файла

В первой строке находится одно целое число $N(1 \leq N \leq 18)$.

Во второй строке находятся $N$ целых числа $a_1,a_2,...,a_N(1 \leq a_i \leq 10^8)$.

Формат выходного файла

Выведите ответ на задачу.

Система оценки

Данная задача состоит из $10$ тестов. Каждый тест оценивается в $10$ баллов.

Тест 1. Пример из условия.

Тесты 2-4: $n=2$.

Тесты 5-7: $1 \leq a_i \leq 9$.

Тесты 8-10: без дополнительных ограничении.

Примеры

Ввод

5
8 45 32 27 111

Вывод

3