B. Matryoshka Inc
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Популярная компания Matryoshka Inc, производящая игрушки, планирует запустить акцию, в ходе которой всем желающим будет предложено решить следующую задачу: в ряд расставлены $$$n$$$ матрешек, пронумерованные от $$$1$$$ до $$$n$$$; $$$i$$$-я из них имеет размер $$$s_i$$$, причем $$$s_i$$$ может иметь лидирующие нули. Участникам предлагается собрать цепочку из как можно большего числа вложенных матрешек. Однако, есть ограничение, что собирать матрешки можно только в порядке слева направо, от меньшей к большей (матрешки можно пропускать, не обязательно использовать все подряд).

Более подробно: участник может взять любую матрешку, затем выбрать другую матрешку строго большего размера и расположенную правее данной, и положить первую внутрь второй. После чего можно снова выбрать матрешку строго большего размера и расположенную правее последней выбранной и положить первые две матрешки (где одна уже находится внутри другой) внутрь третьей. Такой процесс можно повторять сколько угодно раз. Выигрыш участника равен количеству матрешек, которые он использовал в своих действиях, включая последнюю матрешку. В случае, когда никакую матрешку нельзя положить внутрь более правой с большим размером, либо если в ряду стоит всего одна матрешка, то выигрыш участника считается равным единице.

Директора компании заинтересовало, какой максимальный выигрыш сможет получить участник. Чтобы это выяснить, он отправил вам числа $$$s_1, \ldots, s_n$$$ по специальному секретному каналу связи компании Matryoshka Inc. Однако в ходе передачи сообщения произошел сбой, и цифры в числах $$$s_1, \ldots, s_n$$$ перемешались. В итоге вы получили набор чисел $$$a_1, \ldots, a_n$$$, где $$$a_i$$$ — число, полученное из $$$s_i$$$ некоторой перестановкой цифр.

Поскольку до запуска акции осталось всего ничего, времени на повторную отправку нет. Поэтому директор попросил вас найти максимальный возможный выигрыш участника по известным значениям $$$a_1, \ldots, a_n$$$. Учитывайте, что в теории настоящий размер $$$i$$$-й матрешки может быть равен любой перестановке цифр $$$a_i$$$, в том числе содержащей ведущие нули.

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

Первая строка содержит одно число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество матрешек, участвующих в акции.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 10^{18}$$$) — числа, полученные вами по секретному каналу связи. Длина каждого числа, включая ведущие нули, не превосходит $$$18$$$ цифр.

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

Выведите единственное число — максимальный возможный выигрыш, который теоретически может получить участник.

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

Обозначим за $$$L$$$ максимальную длину входного числа $$$a_i$$$.

ПодзадачаБаллыОграничения
112$$$n \le 3$$$
28$$$n \le 18$$$
39$$$L = 1$$$
417$$$L \le 3$$$
526$$$n \le 200, 1 \le L \le 8$$$
628Без дополнительных ограничений
Примеры
Входные данные
2
1 1
Выходные данные
1
Входные данные
5
10 2 30 4 50
Выходные данные
5
Входные данные
6
77 88 91 22 33 44
Выходные данные
4
Входные данные
3
390100 200200 012
Выходные данные
3
Примечание

Рассмотрим первый пример. В акции участвует всего две матрешки с одинаковым размером, равным единице. Поскольку матрешки одинаковых размеров не могут быть вложены друг в друга, длина максимальной цепочки из вложенных матрешек равна $$$1$$$.

Рассмотрим второй пример. Если предпололжить, что настоящие размеры матрешек равны $$$01$$$, $$$2$$$, $$$03$$$, $$$4$$$, $$$05$$$, то участник может собрать цепочку из пяти матрешек. Поэтому ответ на второй пример — $$$5$$$.

Рассмотрим третий пример. В этом случае существует всего два варинта настоящей последовательности размеров матрешек, которую вам отправляли по секретному каналу. Первая из них: $$$77$$$, $$$88$$$, $$$91$$$, $$$22$$$, $$$33$$$, $$$44$$$. Вторая: $$$77$$$, $$$88$$$, $$$19$$$, $$$22$$$, $$$33$$$, $$$44$$$. Как несложно видеть, в первом случае длина максимальной цепочки из матрешек равна $$$3$$$, а во втором случае — $$$4$$$. Поэтому ответ на третий пример  — $$$4$$$.

Рассмотрим четвертый пример. Если предположить, что настоящие размеры матрешек равны $$$000139$$$, $$$000202$$$, $$$210$$$, то участник может собрать цепочку из трех матрешек, сначала вложив первую матрешку внутрь второй, а затем вложив первые две матрешки внутрь третьей. Таким образом, ответ на четвертый пример — $$$3$$$.