**Замечание: Время на тест и ограничение по памяти для этой задачи
3сек и 512MB, что, соответственно, в 1.5 и 2 раза больше чем по умолчанию.**
Каждая из \(N\) (\(1 \leq N \leq 10^5\)) коров Фермера Джона имеет свой ID-номер
в виде битовой строки (строки соcтоящей из символов '0' и '1'). Беси,
старейшая корова, помнит ID-номера всех коров и любит спрашивать у коров
их ID-номера.
Когда у коровы спрашивают ID-номер, они начинают отвечать правильную
битовую строку, но могут забыть и остановиться, не закончив её.
Когда Беси слышит битовую строку, если та не является ID-номером ни одной
коровы на ферме, она пожимает плечами и уходит. Однако если это ID-номер
другой коровы на ферме, она предполагает, что произошла кража личных данных
и закрывает ферму на карантин. Заметим, что это может случиться даже если
корова говорит свой полный правильный ID-номер.
ФД хочет избавиться от последней ситуации и добавить несколько битов к
некоторым ID-номерам. За одну секунду он может добавить один бит в конец
ID-номера любой коровы. Определите минимальное количество времени, которое
потребуется чтобы избежать карантина по совпадению правильного ID-номера.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\), количество коров на ферме у ФД.
Далее следуют \(N\) строк. \(k\)-я строка содержит битовую строку, равную
ID-номеру \(k\)-ой коровы.
Никакой и ID-номеров не пустой, и общая длина всех ID-номеров не более
\(10^6\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите минимальное количество секунд, которое требуется фермеру Джону
чтобы обеспечить, что карантин не случится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
1
1
|
5
|