Sereja 有两个序列 a1, a2, ..., an 和 b1, b2, ..., bm,由整数组成。有一天,塞雷贾感到无聊,他决定和他们一起玩两个。游戏规则非常简单。 Sereja 可以进行多个动作,在一个动作中他可以执行以下操作之一:
1、选择序列a的多个(至少一个)第一个元素(a的非空前缀),选择序列b的多个(至少一个)第一个元素(b的非空前缀);序列a中所选元素中索引最大的元素必须等于序列b中所选元素中索引最大的元素;从序列中删除所选元素。
2. 删除两个序列的所有元素。
第一个动作价值 e 能量单位,并向 Sereja 的电子账户添加 1 美元。第二个动作的能量单位数量等于 Sereja 在执行该动作之前从序列中删除的元素数量。当Sereja执行第二个动作后,他就得到了他在游戏过程中电子账户上赚到的所有钱。
最初,Sereja 有 s 能量单位,但他的账户上没有钱。 Sereja 最多可以获得多少金钱?注意,Seraja 的能量在任何时候都不能为负。
输入
第一行包含整数 n、m、s、e (1 ≤ n, m ≤ 105; 1 ≤ s ≤ 3·105; 103 ≤ e ≤ 104)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 105)。第三行包含 m 个整数 b1, b2, ..., bm (1 ≤ bi ≤ 105)。
输出
打印一个整数——Sereja 可以获得的最大美元金额。
示例
输入 #1
5 5 100000 1000 1 2 3 4 5 3 2 4 5 1
输出 #1
3
输入 #2
3 4 3006 1000 1 2 3 1 2 4 3
输出 #2
2