← 返回题目列表

Codeforces · 425/C

C. Sereja 和两个序列

中文机器翻译题面 查看原题

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