题目背景

春天到了，花园里的花竞相开放。樱花、梅花、梨花、桃花、牡丹都开放了。

你需要在花园里采花。

日文版题面：JP 版リンク。

如果你只会 cout << 1 这样骗分，建议不要浪费时间在这里。

题目描述

这个花园是由位于最左边的两个 $\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$ 值。

输入格式

第一行四个整数，代表 $n,a,b,k$；

接下来一行 $n$ 个整数，第 $i$ 个整数代表第 $1$ 行第 $i$ 格内花的美丽值;

接下来一行 $n$ 个整数，第 $i$ 个整数代表第 $2$ 行第 $i$ 格内花的美丽值;

输出格式

一行一个整数，表示所求答案。

6 5 4 3
1 3 4 6 10 10
1 2 7 8 5 9

1

提示

应要求，本题提供一个大样例，链接在下方。

样例 #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$
3	$n \leq 2500$	40
4	$n \leq 100000$		2s

对于所有数据，$0 \leq f_i,k \leq 10^{8},1 \leq b < a \leq 10^8,n \ge 2$。

提示：

• 可能需要注意常数因子带来的效率差异。
• 本题存在 $O(n \log V)$ 的做法。