这个花园是由位于最左边的两个 $\texttt{start}$ 格子加上 $2 \times n$ 个方格组成的一个长列。如下图，$n=6$：
注意 $n$ 并不包括最左边的两个 $\texttt{start}$ 格子。每个格子里面都有一棵花，花的美丽程度（下称“**美丽值**”）用一个整数表示，在上图中已经写在格子里了。
从**最左边任选**一个 $\texttt{start}$ 格子开始，每个时刻，你可以走到当前格子**右**、**右上**或**右下**的格子（只要不走出界），并采走里面的花。当走到花园**尽头**时结束。
然后你需要把采到的花按照美丽程度**升序排列**，组成一串花。记**排序过后的**花串中第 $i$ 朵花的美丽值为 $f_i$，那么这串花的“和谐度”$F$ 等于：
$$F = \min_{i=1}^{n-1} \begin{cases} k \times |f_i-f_{i+1}| && |f_i-f_{i+1}| \bmod b = a \\ |f_i-f_{i+1}| && |f_i-f_{i+1}| \bmod b \not = a\\\end{cases}$$
现在知道了花园中每个格子内的花的美丽值，你需要计算出可能的**最大** $F$。即在所有可能的行走方案中，可能出现的最大的 $F$ 值。
## Input
第一行四个整数，代表 $n,a,b,k$；
接下来一行 $n$ 个整数，第 $i$ 个整数代表第 $1$ 行第 $i$ 格内花的美丽值;
接下来一行 $n$ 个整数，第 $i$ 个整数代表第 $2$ 行第 $i$ 格内花的美丽值;
## Output
一行一个整数，表示所求答案。
[samples]
## Background
春天到了，花园里的花竞相开放。樱花、梅花、梨花、桃花、牡丹都开放了。
你需要在花园里采花。
日文版题面：[JP 版リンク](https://www.luogu.com.cn/problem/T239022)。
如果你只会 `cout << 1` 这样骗分，建议不要浪费时间在这里。
## Note
**应要求，本题提供一个大样例，链接在下方。**
样例 #1 解释：
一条路径如下图：
按时间顺序，得到的花的美丽值为 $\{1,2,4,6,5,10\}$；排序后为 $\{1,2,4,5,6,10\}$，可以计算出 $F=1$，这是能得到最大的 $F$ 了。
如果您无法写出能够得到满分的程序，可参考如下数据范围获取部分分值：
| 编号 | 特殊限制 | 分值 | 时限 |
| :----------: | :----------: | :----------: | :----------: |
| 1 | $n \leq 30$ | 10 | 1s |
| 2 | $n\leq 100$ | 10 | 1s |
| 3 | $n \leq 2500$ | 40 | 1s |
| 4 | $n \leq 100000$ | 40 | 2s |
对于所有数据，$0 \leq f_i,k \leq 10^{8},1 \leq b < a \leq 10^8,n \ge 2$。
提示：
- 可能需要注意常数因子带来的效率差异。
- 本题存在 $O(n \log V)$ 的做法。