Задан набор из n строк ti. Для каждой строки известна ее стоимость ci.
Определим следующую функцию от строки 
, где ps, i — число вхождений строки s в строку ti, а |s| — длина строки s. Найдите максимальное значение функции f(s) по всем строкам.
Обратите внимание, что s — это не обязательно строка из заданного набора t.
Выходные данные
В единственной строке выходного файла выведите целое число a — наибольшее значение функции f(s) по всем строкам s. Обращаем еще раз внимание, что строка s не обязательно из заданного набора t.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
aa
bb
2 1
|
4
|
|
2
|
2
aa
ab
2 1
|
5
|