Дана строка s, состоящая из n строчных латинских букв. Некоторые индексы в этой строке являются запрещёнными.
Вам необходимо найти такую строку a, что значение |a|·f(a) является максимально возможным, где f(a) — количество вхождений a в s, заканчивающихся в индексах, не являющихся запрещёнными. Например, если s — aaaa, a — aa и индекс 3 — запрещённый, то f(a) = 2, так как a встречается в s три раза (начиная с индексов 1, 2 и 3), но одно из этих вхождений (то, которое начинается в индексе 2) заканчивается в запрещённом индексе.
Посчитайте максимально возможное значение |a|·f(a).
Выходные данные
Выведите максимально возможное значение |a|·f(a).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
ababa
00100
|
5
|
|
2
|
5
ababa
00000
|
6
|
|
3
|
5
ababa
11111
|
0
|