Задача Набор строк

Описание

В Инновационном Отделе НИИ Исследований Данных Строк разработана клавиатура для внутреннего пользования, облегчающая набор строк огромной длины. Кроме обычных клавиш, соответствующих маленьким латинским буквам, на клавиатуре есть еще n функциональных клавиш F ₁ , . . . , F _n , соответствующих заданным строкам из словаря S ₁ , . . . S _n . При нажатии такой клавиши F _i строка S _i загружается во внутреннюю память клавиатуры. В каждый момент времени в памяти может находиться не более одной строки из словаря.

Кроме того, в клавиатуру встроен графический манипулятор "Кыш", с помощью которого легким движением руки можно ввести любую подстроку находящейся в памяти строки.

Вася занимается исследованием эффективности данного нововведения. Для этого ему требуется написать программу, которая будет вычислять минимальное необходимое количество действий (нажатий и использований "Кыш" ) для ввода данной строки S . В момент начала ввода строки память пуста.

Например, если требуется ввести строку "abacaba", а в словаре есть строки "baba" и `"caca", то это можно сделать за четыре действия - нажать F ₁ , выбрать манипулятором подстроку "aba", затем нажать "c", и опять выбрать манипулятором подстроку "aba". Если бы нужно было набрать с таким словарем "bacababa" , то это можно сделать за пять действий: "b" , F ₂ , "aca", F ₁ , "baba".

Формат входных данных

В первой строке входного файла задано число n (1 ≤ n ≤ 50) . В последующих n строках заданы S _i , составленные из не более чем 500 символов. В последней строке вводится непустая строка S , длина которой не превосходит 100000 . Все символы строк - маленькие латинские буквы.

Формат выходных данных

Выведите минимальное необходимое количество действий.