出题人：宋浩然

题目描述

为了检验你的字符串基础是否扎实，给定 $2n$ 个字符串和正整数 $k$，前 $n$ 个记作 $a_i$，后 $n$ 个记作 $b_i$，保证所有字符串长度均不超过 $k$。

但是在字符串专项训练中需要出现矩阵，令 $c_{i,j}=k-\operatorname{LCP}(a_i,b_j)$。

现在需要对这个矩阵做神法，每次可以若干代价对矩阵 $c$ 做下列操作之一：

• 选择 $i$，$c_{i,j}\leftarrow c_{i,j}-1(1\le j\le n)$，代价为 $1$。

• 选择 $j$，$c_{i,j}\leftarrow c_{i,j}-1(1\le i\le n)$，代价为 $1$。

• 选择 $i$，$c_{i,j}\leftarrow c_{i,j}+1(1\le j\le n)$，代价为 $-1$。

• 选择 $j$，$c_{i,j}\leftarrow c_{i,j}+1(1\le i\le n)$，代价为 $-1$。

• 选择 $i,j$，$c_{i,j}\leftarrow c_{i,j}-1$，代价为 $1$。

因为多测要清零，不能共存，求让矩阵 $c$ 清零的最小代价。

输入格式

为了选手方便（出题人偷懒），所以本题不以 Trie 树作为输入。

第一行两个正整数 $n,k$。

接下来 $n$ 行，第 $i$ 行一个字符串 $a_i$。

接下来 $n$ 行，第 $i$ 行一个字符串 $b_i$。

保证 $a_i,b_i$ 由小写英文字母组成。

输出格式

一行一个正整数为答案。

样例1

输入

3 4
aaab
bab
aab
ab
aabb
abb

输出

11

样例2

输入

3 10
aaaabab
ababbbba
aaaabba
ababaa
aaaabaaaa
aabbbaa

输出

31

样例3/4

见下发文件中 $\text{ex_matrix3/4.in/ans}$

数据范围

对于 $10\%$ 的数据，$n\le3,|a_i|,|b_i|,k\le10$。

对于 $40\%$ 的数据，$n\le100,\sum|a_i|,\sum|b_i|\le200,k\le300$。

对于 $50\%$ 的数据，$n\le1000$。

对于另外 $20\%$ 的数据，所有字符串由只包含字母 a。

对于所有数据，$1\le n\le10^6,\sum|a_i|,\sum|b_i|\le2\times10^6,1\le|a_i|,|b_i|\le k\le2\times10^6$。

大样例