问题描述

作为一个 qboi 的管理员，Terence 每天的任务就是：删除一些恶意死循环的代码，并让一些正确的代码 AC。

qboi 有一个代码生成器，会将提交到上面的程序变成一段代码。有 n 段代码。

如果代码 a[i]里面有字符串 s1，则这段代码是恶意死循环代码，要删去。如果代码 a[j]里面有字符串 s2，则这段代码是 AC 代码，要让他通过。如果代码 a[g]中既没有 s1，也没有 s2，那么 Terence 就不用处理这条代码。对于代码 a[i]，操作时间是 v[i]。

Terence 很忙，因为他要玩 OW（这个世界需要更多的英雄）。

所以他只有 t 的时间去完成这件事，但他不知道如何才能尽可能的多的删除或通过这些代码，所以找到了会编程的你，让你帮他计算。

输入格式

第一行输入 n,t；

第二行输入 s1。

第三行输入 s2。

剩下 n 行：对于第 i 行，输入代码 a[i]，和操作代码所需时间 v[i]。

输出格式

输出共一行。

第一行输出 Terence 可以删除或通过的代码最多数。

输入样例

4 5
hzd
zly
weqewywhzd 3
Hzdfwfu 543
fjthzlyert 2
fgrrgggehq 666

输出样例

2

注释说明

对于所有的数据，1000<=n<=5000，代码长度<=100； 1<=strlen(s1)，strlen(s2)<=10; 1<=v[i]<=100，1000<=t<=500000.

保证数据合法，不会出现一条代码同时包含 s1,s2 的情况