出题人:宋浩然
题目描述
为了检验你的字符串基础是否扎实,给定 $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$。