Умный Бобер из ABBYY уже давно сотрудничает с НИИ «Цитологии и Генетики». Недавно работники этого НИИ предложили Бобру новую задачу. Суть задачи заключалась в следующем.

Есть набор из n белков (не обязательно различных). Каждый белок представляет собой строку, состоящую из маленьких букв латинского алфавита. Задача, которую поставили перед Умным Бобром ученые, заключается в выборе поднабора мощности k из исходного набора белков, причём репрезентативность выбранного поднабора белков должна быть максимальной.

Умный Бобер из ABBYY провел небольшое исследование и пришел к выводу, что репрезентативность набора белков можно оценить одним числом, которое достаточно просто вычисляется. Пусть у нас есть набор {a₁, ..., a_k} из k строк, описывающих белки. Репрезентативностью этого набора называется следующая величина:

где f(x, y) — длина наибольшего общего префикса строк x и y; например, f(«abc», «abd») = 2, а f(«ab», «bcd») = 0.

Таким образом, репрезентативность набора белков {«abc», «abd», «abe»} равна 6, а набора {«aaa», «ba», «ba»} — 2.

После этого открытия Умный Бобер из ABBYY обратился к участникам Cup'а с просьбой написать программу, выбирающую из заданного набора белков поднабор мощности k, который имеет наибольшее возможное значение репрезентативности. Помогите ему с решением этой задачи!