Background

Spring has arrived, and the flowers in the garden are blooming one after another. Cherry blossoms, plum blossoms, pear blossoms, peach blossoms, and peonies have all bloomed.

You need to pick flowers in the garden.

Japanese statement: JP version link。

If you only know how to get points by doing cout << 1, it is recommended not to waste your time here.

Problem Description

This garden consists of the two leftmost $\texttt{start}$ cells plus a long strip of $2 \times n$ cells. As shown below, $n=6$:

Note that $n$ does not include the two leftmost $\texttt{start}$ cells. Each cell contains a flower. The beauty of a flower (hereinafter called the "beauty value") is represented by an integer, which has already been written inside each cell in the figure above.

Starting from either of the leftmost $\texttt{start}$ cells, at each moment you may move to the cell to the right, upper-right, or lower-right of the current cell (as long as you do not move out of bounds), and pick the flower in that cell. The process ends when you reach the end of the garden.

Then you need to sort the picked flowers by beauty value in non-decreasing order to form a sequence. Let the beauty value of the $i$-th flower in the sorted sequence be $f_i$. Then the "harmony" $F$ of this sequence is:

$$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}$$

Now, given the beauty values of the flowers in every cell of the garden, you need to compute the maximum possible $F$. That is, among all possible walking paths, find the largest $F$ that can occur.

Constraints

If you cannot write a program that gets full score, you may refer to the following constraints to obtain partial scores:

ID	Special Restriction	Score	Time Limit
1	$n \leq 30$	10	1s
2	$n\leq 100$
3	$n \leq 2500$	40
4	$n \leq 100000$		2s

For all data, $0 \leq f_i,k \leq 10^{8},1 \leq b < a \leq 10^8,n \ge 2$。

Input Format

The first line contains four integers $n, a, b, k$.

The next line contains $n$ integers. The $i$-th integer represents the beauty value of the flower in row $1$, column $i$.

The next line contains $n$ integers. The $i$-th integer represents the beauty value of the flower in row $2$, column $i$.

Output Format

Output one integer per line, the required answer.

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

1

Hint

As requested, this problem provides a large sample. The link is below.

Sample #1 explanation:

One path is shown below:

In time order, the collected beauty values are $\{1,2,4,6,5,10\}$. After sorting, they become $\{1,2,4,5,6,10\}$. We can compute $F=1$, and this is the maximum $F$ that can be achieved.

Hints:

• You may need to pay attention to efficiency differences caused by constant factors.
• There is an $O(n \log V)$ solution for this problem.

Translated by ChatGPT 5