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