Слияние городов
Недавние достижения в области информационных и коммуникационных технологий позволили предоставлять муниципальные услуги на более обширной территории быстрее и с меньшими затратами. Вследствие этого, а также, вероятно, для экономии ограниченных ресурсов, мэры многих городов начали обсуждать возможность объединения своих городов.
Конечно, существует множество препятствий для фактического осуществления запланированных слияний. У каждого города есть своя культура, которой гордятся его жители. Одним из главных источников разногласий является название нового города. Все жители настаивают на том, чтобы в названии нового города было хотя бы частично сохранено оригинальное название их собственного города. Однако простое объединение всех оригинальных названий сделает название слишком длинным для повседневного использования.
Группа мэров обратилась к вам с просьбой написать программу, которая находит самое короткое возможное название для нового города, включающее все оригинальные названия объединяемых городов. Если у двух или более городов есть общие части, они могут быть наложены друг на друга. Например, если города "FUKUOKA", "OKAYAMA" и "YAMAGUCHI" должны быть объединены, "FUKUOKAYAMAGUCHI" — это такое название, которое включает все три оригинальных названия городов. Хотя это включает все символы названия города "FUKUYAMA" в этом порядке, оно не появляется как последовательная подстрока, и, следовательно, "FUKUYAMA" не считается включенным в название.
Входные данные
Входные данные состоят из последовательности наборов данных. Каждый набор данных начинается со строки, содержащей положительное целое число n (n ≤ 14), которое обозначает количество городов, подлежащих слиянию. Следующие n строк содержат названия городов заглавными буквами латинского алфавита, по одному в каждой строке. Можно предположить, что ни одно из оригинальных названий городов не превышает 20 символов. Конечно, ни у двух городов нет одинакового названия.
Конец ввода обозначается строкой, состоящей из нуля.
Выходные данные
Для каждого набора данных выведите длину самого короткого возможного названия нового города в одной строке.
Вывод не должен содержать никаких других символов.