P8358 "WHOI-1" HanawoTori

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](https://www.luogu.com.cn/problem/T239022)。 If you only know how to get points by doing `cout

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$ | 10 | 1s | | 3 | $n \leq 2500$ | 40 | 1s | | 4 | $n \leq 100000$ | 40 | 2s | For all data, $0 \leq f_i,k \leq 10^{8},1 \leq b < a \leq 10^8,n \ge 2$。

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 one integer per line, the required answer.

**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