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