CF425C Sereja and Two Sequences

Sereja 有两个整数序列 $a_{1}, a_{2}, \ldots, a_{n}$ 和 $b_{1}, b_{2}, \ldots, b_{m}$。有一天，Sereja 感到无聊，决定用这两个序列玩一个游戏。游戏的规则非常简单。在每一步中，Sereja 可以进行下列操作之一： 1. 选择序列 $a$ 的若干（至少一个）开头元素（即 $a$ 的非空前缀），选择序列 $b$ 的若干（至少一个）开头元素（即 $b$ 的非空前缀）；所选 $a$ 中下标最大的元素必须与所选 $b$ 中下标最大的元素相等；将这些选中的元素从各自的序列中移除。 2. 将两个序列的所有元素全部移除。 执行第一种操作会消耗 $e$ 单位能量，并且会让 Sereja 的电子账户增加 1 美元。执行第二种操作会消耗的能量等于 Sereja 在执行该操作前已经从两个序列中移除的元素总数。在执行第二种操作后，Sereja 会获得此前在电子账户中累计的所有美元。 初始时，Sereja 拥有 $s$ 单位能量，且账户中没有钱。Sereja 在任何时刻拥有的能量不能小于 0。请问，Sereja 最多能获得多少美元？

第一行包含整数 $n$，$m$，$s$，$e$，满足 $1 \leq n, m \leq 10^5$，$1 \leq s \leq 3 \times 10^5$，$10^3 \leq e \leq 10^4$。 第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$，满足 $1 \leq a_{i} \leq 10^5$。 第三行包含 $m$ 个整数 $b_{1}, b_{2}, \ldots, b_{m}$，满足 $1 \leq b_{i} \leq 10^5$。

输出一个整数，表示 Sereja 最多可以获得的美元数。

由 ChatGPT 5 翻译