题目描述

在最后一次抢劫中，四骑士把一名黑客送进了联邦银行严密保护的系统。他的任务是在触摸键盘上输入一串特定的单词，破解安全模块。

安全模块中有 $n$ 个单词，均由小写拉丁字母组成。杰克很快发现，只要输入其中任意 $k$ 个单词就能完成破解，单词可以重复选择。除了最后一个单词，每个单词后都必须输入一个空格。空格由另一根手指输入，因此输入空格不花费时间。

为了输入一个字母，杰克需要把输入字母的手指从当前按键移动到相应按键，耗时等于两个按键之间的距离。按下手指当前所在的按键不花费时间。

键盘由三行组成，每行长度为 $9$。键盘上包含所有拉丁字母和一个空格键。两个按键之间的距离为它们坐标差的绝对值之和：从 $(x_1,y_1)$ 移动到 $(x_2,y_2)$ 需要 $|x_2-x_1|+|y_2-y_1|$ 单位时间。

开始时，杰克可以把手指放在任意按键上。求他完成破解至少需要多少时间。

输入格式

第一行包含两个整数 $n,k$，满足 $1\le n\le10^5$，$1\le k\le10^9$。

接下来 $n$ 行，每行包含一个单词 $s$，满足 $1\le |s|\le10^6$。所有单词的长度之和不超过 $10^6$。

接下来给出键盘布局，共三行，每行恰有 $9$ 个字符。保证空格键的坐标为 $(3,5)$，即第三行正中间。其余字符都是互不相同的小写拉丁字母。

输出格式

输出一行，包含本题的答案。

3 2
abba
zaaz
aaaz
abcdefghi
jklmnopqr
stuv wxyz

4

3 2
abba
zaaz
aaaz
aczdefghi
jklmnopqr
stuv wxyb

6

2 1000000000
aaaab
bbbba
azcdefghi
jklmnopqr
stuv wxyb

10000000000