题目描述

比瑟姆顿大学仅由一条公交线路提供服务。在前往市中心的途中，它设有几个站点，学生可以在这些站点下车。每个学生都有固定的想要下车的公交站。

现在是周五下午 4 点，和往常一样，所有学生都想回家，导致公交站排起了长队。幸运的是，这条公交线路有规律的间隔，第一班车在下午 4 点到达。

每当一辆公交车到达大学时，队伍中的每个人都试图上车，这使得公交车非常拥挤。这导致了许多投诉，人们试图下车但由于人太多而无法下车。因此，公交公司决定，在车上有人要下车的每一个站点，车上的所有人都必须下车。那些想要继续旅行的人再重新上车。每次乘客上车或下车，公交车需要等待 $w$ 秒。

为了提供最好的服务，公交公司希望最小化从下午 4 点开始直到每个人到达目的地所需的最大时间。对于每辆公交车，司机可以决定让队伍前面多少人上车。可以上车的人数没有限制。帮助公交司机做出最优决策，以实现公司的目标。

输入格式

输入包含：

• 一行四个整数 $n$、$b$、$r$ 和 $w$（$1 \leq n, b \leq 10^5$，$1 \leq r, w \leq 10^6$），分别表示乘客数量、公交站数量、两辆公交车到达大学的时间间隔，以及上下车造成的延迟。
• 一行 $b$ 个整数 $d_i$（$1 \leq d_i$，$\sum d_i \leq 10^6$），表示从第 $(i-1)$ 个公交站到第 $i$ 个公交站的行驶时间（第 0 个公交站是大学）。
• 一行 $n$ 个整数 $t_i$（$1 \leq t_i \leq b$），表示队伍中第 $i$ 个人的目的地是第 $t_i$ 个公交站。

所有时间均以秒为单位。

输出格式

输出一个整数，表示直到队伍中每个人都到达其目的地所需的最少秒数。

3 3 20 1
2 2 2
2 3 1

18

4 2 1 10
3 2
1 2 2 1

27

5 3 3 3
2 2 1
3 3 2 1 1

17

提示

样例 1 解释

在这个例子中，最优方案是让所有人都上第一辆车。第一次上车耗时 3 秒。然后，公交车行驶 2 秒到达 1 号公交站。3 秒后，所有人下车，再经过 2 秒，继续行程的人重新上车。再经过 2 秒，他们到达下一个站点，在那里所有人下车耗时 2 秒，剩下的一人重新上车耗时 1 秒。再经过 2 秒，公交车到达最终目的地，最后一人下车耗时 1 秒。

样例 2 解释

最优方案是每人一辆车。

样例 3 解释

最优方案是将前两名乘客分配至一辆车，其余每人一辆车。

翻译由 DeepSeek 完成