Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

出题人:宋浩然

题目描述

为了检验你的字符串基础是否扎实,给定 $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$。

大样例