Однажды Вася и Петя придумали новую игру и назвали ее «Умный мальчик». Для игры они зафиксировали некоторый набор слов — словарь. Допускается, что словарь содержит одинаковые слова.
Правила игры таковы: сначала первый игрок выбирает любую букву (слово длины 1) из любого слова из словаря и записывает ее на лист бумаги. Второй игрок приписывает к этой букве некоторую другую в начало или в конец, таким образом получая уже слово длины 2, затем опять ходит первый игрок, и он опять приписывает некоторую букву в начало или в конец, получая слово длины 3. И так далее. Но игрок не имеет права нарушать условие: новое записанное слово должно являться подстрокой некоторого слова из словаря. Проигрывает тот, кто не может увеличить текущую строку так, чтобы не нарушалось условие.
Также если после хода на бумаге записана некоторая строка s, то игрок, сделавший этот ход, получает количество очков по формуле:
где:
-
— порядковый номер символа c в латинском алфавите, пронумерованном с 1. Например, 
, а 
. -
— количество слов из словаря, где встречается строка s как подстрока хотя бы один раз.
Ваша задача — узнать, кто выиграет в этой игре, и итоговый счет. Каждый игрок играет оптимально, и в первую очередь стремится выиграть, во вторую — максимизировать свои очки, в третью — минимизировать очки соперника.