拥挤的公交车。图源：Pexels/Pew Nguyen

Bithampton 大学只有一条公交线路服务。在前往市中心的途中，它会经过几个学生可以下车的车站。每个学生都有一个固定的下车车站。

现在是周五下午 4 点，和往常一样，所有学生都想回家，导致公交车站排起了长队。幸运的是，公交线路以固定的时间间隔运行，第一辆公交车于下午 4 点到达。

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

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

输入格式

输入包含以下内容：

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

所有时间均以秒为单位。

输出格式

输出所有人均已在目的地下车所需的最小秒数。

样例

输入格式 1

3 3 20 1
2 2 2
2 3 1

输出格式 1

18

说明 1

在这个样例中，让所有人登上第一辆公交车是最优的。第一次上车需要 3 秒。然后，公交车行驶 2 秒到达 1 号车站。3 秒后，所有人下车，再过 2 秒，继续行程的人重新上车。再行驶 2 秒后，他们到达下一个车站，所有人下车需要 2 秒，剩下的人重新上车需要 1 秒。再行驶 2 秒后，公交车到达终点站，最后一个人下车需要 1 秒。

输入格式 2

4 2 1 10
3 2
1 2 2 1

输出格式 2

27

说明 2

每人乘坐一辆公交车是最优的。

输入格式 3

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

输出格式 3

17

说明 3

将前两名乘客分配到同一辆公交车，其余每个人单独乘坐一辆公交车是最优的。