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

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

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Ввод

5
8 45 32 27 111

Вывод

3