Хакерская задача
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время финального ограбления «Четыре Всадника» внедряют хакера внутрь защищённой системы федерального банка. Его задача — взломать защитный модуль, набрав специальную последовательность слов на сенсорной клавиатуре.

В защитном модуле есть набор из $$$n$$$ слов, состоящих из строчных латинских букв. Джек быстро понял, что для взлома достаточно написать какие-то $$$k$$$ слов из набора, причём слова могут повторяться, а после каждого слова, кроме последнего, должен идти пробел (пробелы печатаются отдельным пальцем, так что на их написание время не тратится). Чтобы написать какую-то букву, Джек должен переместить палец с текущей кнопки на другую кнопку, при чём он тратит на это действие время, равное расстоянию между начальной и конечной кнопками. Время на нажатие кнопки, на которой находится палец, не тратится.

Клавиатура задана тремя строками длины 9. На ней есть все буквы латинского алфавита, а также один пробел. Расстояние между кнопками считается как сумма абсолютной разницы координат кнопок (то есть чтобы из кнопки ($$$x_1;\ y_1$$$) дойти до кнопки ($$$x_2;\ y_2$$$), нужно потратить $$$|x_2 - x_1| + |y_2 - y_1|$$$ единиц времени).

Найдите минимальное количество времени, которое Джеку придётся потратить на взлом, при условии, что изначально он может поставить палец на любую кнопку.

Входные данные

В первой строке вводится два числа $$$n$$$, $$$k$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le k \le 10^9$$$).

В следующих $$$n$$$ строках вводится по одному слову $$$s$$$ ($$$1 \le |s| \le 10^6$$$). Гарантируется, что сумма длин всех слов не превосходит $$$10^6$$$.

Далее идёт описание клавиатуры: три строки из $$$9$$$ символов. Гарантируется, что пробел имеет координаты ($$$3; 5$$$), то есть находится в середине третьей строки. Все остальные символы — неповторяющиеся строчные буквы латинского алфавита.

Выходные данные

В единственной строке выведите ответ на задачу.

Примеры

Входные данные

    3 2abbazaazaaazabcdefghijklmnopqrstuv wxyz

Выходные данные

    4

Входные данные

    3 2abbazaazaaazaczdefghijklmnopqrstuv wxyb

Выходные данные

    6

Входные данные

    2 1000000000aaaabbbbbaazcdefghijklmnopqrstuv wxyb

Выходные данные

    10000000000