CF425C.Sereja and Two Sequences

Sereja has two sequences _a_1, _a_2, ..., a__n and _b_1, _b_2, ..., b__m, consisting of integers. One day Sereja got bored and he decided two play with them. The rules of the game was very simple. Sereja makes several moves, in one move he can perform one of the following actions:

1. Choose several (at least one) first elements of sequence a (non-empty prefix of a), choose several (at least one) first elements of sequence b (non-empty prefix of b); the element of sequence a with the maximum index among the chosen ones must be equal to the element of sequence b with the maximum index among the chosen ones; remove the chosen elements from the sequences.
2. Remove all elements of both sequences.

The first action is worth e energy units and adds one dollar to Sereja's electronic account. The second action is worth the number of energy units equal to the number of elements Sereja removed from the sequences before performing this action. After Sereja performed the second action, he gets all the money that he earned on his electronic account during the game.

Initially Sereja has s energy units and no money on his account. What maximum number of money can Sereja get? Note, the amount of Seraja's energy mustn't be negative at any time moment.

谢列亚有两组整数序列：$a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_m$。一天，谢列亚感到无聊，决定用它们来玩游戏。游戏规则非常简单：谢列亚进行若干次操作，每次操作可以执行以下两种动作之一：

1. 从序列 $a$ 中选取若干（至少一个）最前面的元素（即 $a$ 的一个非空前缀），同时从序列 $b$ 中也选取若干（至少一个）最前面的元素（即 $b$ 的一个非空前缀）；要求所选 $a$ 中下标最大的那个元素，与所选 $b$ 中下标最大的那个元素相等；然后将这些被选中的元素从各自序列中删除。
2. 将两个序列的所有剩余元素全部删除。

第一种动作消耗 $e$ 单位能量，并为谢列亚的电子账户增加 1 美元。第二种动作所消耗的能量单位数等于执行该动作时从两个序列中总共删除的元素个数。在谢列亚执行第二种动作后，他将获得其在整个游戏中电子账户上累计赚得的全部金额。

初始时，谢列亚拥有 $s$ 单位能量，且电子账户余额为零。问：谢列亚最多能获得多少美元？注意：在任意时刻，谢列亚的能量值均不得为负。

The first line contains integers n, m, s, e (1 ≤ n, m ≤ 105; 1 ≤ s ≤ 3·105; 103 ≤ e ≤ 104). The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 105). The third line contains m integers _b_1, _b_2, ..., b__m (1 ≤ b__i ≤ 105).

第一行包含整数 $n$、$m$、$s$、$e$（$1 ≤ n, m ≤ 10^5$；$1 ≤ s ≤ 3·10^5$；$10^3 ≤ e ≤ 10^4$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 ≤ a_i ≤ 10^5$）。
第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 ≤ b_i ≤ 10^5$）。

Print a single integer — maximum number of money in dollars that Sereja can get.

输出一个整数——Sereja 能获得的最大美元金额。