### 问题描述 $2023$ 年 $8$ 月 $22$ 日，农历七月初七，小秋见证了 Ocharin 和 Cai_Guang 美好的一天。 因为 $2023$ 年 $8$ 月 $20$ 日的某场比赛，让他们都垂头丧气的，准备了一个暑假，结果却不如人意。但为了不影响后面的比赛，他们准备在七夕节好好地玩一天。可是，他们为什么要拉上小秋来当电灯泡呢？ 说来话长，Cai_Guang 很喜欢塔菲波原神，但更喜欢塔菲波原神里的塔菲项链，Ocharin 是一个非常具有浪漫情怀的人，因此 Ocharin 想送给 Cai_Guang 很多很多的塔菲项链。Ocharin 认为，塔菲项链的数量越多，Cai_Guang 就会越喜欢他。 小镇上只有一家店铺卖塔菲项链，但是这家店铺卖的塔菲项链实在是太多了，并且很多都杂乱的堆在仓库里面，因此老板也不知道这些塔菲项链具体的价格。但老板为了防止某点评软件上被评论黑心店铺，于是老板在前台摆了 $m$ 条互不相同的塔菲项链样品（样品不会销售），每条项链都有它的价格。只要顾客能在前台找到与想要购买的塔菲项链完全一致的样品，就能以样品的标价购买这条项链。如果找不到的话，老板就会说顾客买的这条项链是珍宝，顾客就只能花 $k$ 元来购买这条项链。因为是“珍宝”，所以 $k$ 一定比前台任意一条塔菲项链样品的标价贵。 众所周知，项链都是一个环，塔菲项链也不例外。两条塔菲项链完全相同，当且仅当两条塔菲项链的包含宝石数量相同，且两条项链各自至少存在一个起点，使得这两条项链从各自的起点开始，顺时针或逆时针数任意数量的宝石都是相同的。 组成塔菲项链宝石的种类并不多，通常会把不同的宝石种类映射到 $26$ 个小写字母中。但一条塔菲项链包含的宝石数量很多，描述一条塔菲项链时，通常会随机选择项链上的一颗宝石，然后沿着顺时针或则逆时针的方向，往后数这条塔菲项链大小的宝石，按顺序记录每颗宝石对应的字母。 Ocharin 这次带了 $x$ 元，他想要小秋帮助他尽可能多的买到项链，但是小秋也不会，所以找到你来帮忙，你能编写一个程序来帮助小秋吗？注意，仓库中的塔菲项链，每条只能被购买一次。 ### 输入格式 第 $1$ 行输入 $4$ 个整数 $m , n , k,x$，表示塔菲项链的样品数，仓库的塔菲项链数量，当前台不能找匹配的塔菲项链时，购买一条塔菲项链需要的价格和 Ocharin 这次带的钱。 接下来 $m$ 行，每行输 $1$ 个整数 $v$ 和 $1$ 个只包含小写字母的字符串 $s$，第 $i$ 行表示第 $i$ 个塔菲项链样品的标价和这条项链的描述。 接下来 $n$ 行，每行输入 $1$ 个只包含小写字母的字符串，第 $i$ 行表示仓库中第 $i$ 条塔菲项链的描述。 注意，本题输入规模较大，建议采用较快的读入方式。 ### 输出格式 输出仅 $1$ 行，包含 $1$ 个整数，表示 Ocharin 最多能买到的塔菲项链数量。 ### 样例输入 ``` 2 5 10 20 2 abcde 3 aabab bcdea sdfwrew efg babaa edcba ``` ### 样例输出 ``` 4 ``` ### 说明 仓库中第 $1,5$ 条项链与样品 $1$ 完全相同，两条都购买花费 $4$ 元。 仓库中第 $4$ 条项链与样品 $2$ 完全相同，购买花费 $3$ 元。 仓库中剩余的项链没有任何样品与之完全相同。 剩下 $13$ 只能购买 $1$ 条项链。 因此最多可以购买 $4$ 条项链。 ### 评测数据规模 对于 $100$% 的评测数据，$1 \leq n\leq 10^5 , 1 \leq m, x , k , w \leq 2 \times 10^3$。 数据保证：评测数据输入的所有字符串长度之和不超过 $2\times10^6$。