字符串集合

时间限制:50s      空间限制:512MB

题目描述

有三个字符串集合, Pre 、 Mid 和 Suf 。我们称一个字符串的二元组 (p, q) 合法,当且仅当:
1. p 属于集合 Pre ;
2. q 属于集合 Suf ;
3. 存在 p 的一个长度不小于 k1 的子串 p'、 q 的一个长度不小于 k2 的子串 q' ,以及集合 Mid 中的一个字符串 s ,使得 p' + q' 是 s 的一个子串。这里的 + 代表字符串的连接。
你可以进行任意次操作,一次操作中,你需要选择一个合法的二元组 (p, q) ,并从集合 Pre 中删去字符串 p ,从集合 Suf 中删去字符串 q 。求最多的操作次数。


输入格式

输入的第一行包含三个正整数 s1 、 s2 和 s3 ,分别代表集合 Pre 、 Mid 和 Suf 中字符串的个数。
第二行包含两个正整数 k1 和 k2 ,含义如问题描述中所述。
接下来 s1 行,每行包含一个字符串,代表集合 Pre 中的一个字符串。
接下来 s2 行,每行包含一个字符串,代表集合 Mid 中的一个字符串。
接下来 s3 行,每行包含一个字符串,代表集合 Suf 中的一个字符串。


输出格式

输出一行,包含一个正整数,表示最多可以操作的次数。


样例输入

2 1 4
2 3
aab
bbb
aabbcdd
cdd
bcd
zz
bcde

样例输出

2

提示

样例中合法的二元组有 (aab, bcd) 、 (aab, bcde) 和 (bbb, ccd) 。
字符串 zz 的长度小于 k2 ,因此不存在包含这个字符串的合法二元组。
数据规模和约定
令 len(S) 为集合 S 中所有字符串的长度和。再令 L = max{len(Pre), len(Mid), len(Suf)} 。
对于 10% 的数据, s1, s2, s3 ≤ 5 , L ≤ 30 。
对于 20% 的数据, s1, s2, s3 ≤ 30 , L ≤ 300 。
对于 50% 的数据, s1, s2, s3 ≤ 500 , L ≤ 10000 。
对于 100% 的数据, s1, s2, s3 ≤ 25000 , L ≤ 50000 , 0 ≤ k1, k2 ≤ L 。字符串只含有小写英文字母。
注意题目中的“集合”和数学中定义的集合不同,其中可以有相同的字符串。
尚无数据,请不要提交!求此题数据!


题目来源

2014年国家集训队十五人互测

Menuappsclose