Garden Harmony

You are given a garden that consists of a long column of cells. The garden is formed by two special start cells on the far left (which are not counted in n) and a grid of 2 \times n cells to the right. Each of these 2 \times n cells contains a flower with an integer beauty value.

The process is as follows: first, you choose one of the two start cells arbitrarily. Then, at each step, you move from the current cell to one of the three neighboring cells in the next column: directly right, right‐up, or right‐down (as long as you do not go out of bounds). When you reach the end of the garden (i.e. after moving through n columns), your journey terminates.

From the garden, exactly n flowers are collected (one from each column of the 2 \times n grid, note that the start cells are not included in the final collection). Then, you sort the collected flower values in non‐decreasing order to form a flower sequence. Let the sorted values be \(f_1, f_2, \dots, f_n\). The "harmony" \(F\) of the flower sequence is defined as follows:

[ F = \min_{i=1}^{n-1} \begin{cases} ; k \times |f_{i} - f_{i+1}|, & \text{if } |f_{i} - f_{i+1}| \bmod b = a,\[6mm] ; |f_{i} - f_{i+1}|, & \text{if } |f_{i} - f_{i+1}| \bmod b \neq a.\end{cases} ]

Your task is to find the maximum possible harmony \(F\) over all valid paths. Note that because the final flower sequence is sorted, the order in which the flowers were collected does not matter; only the multiset of values matters.

Input constraints: The first line contains four integers n, k, a, and b. Here, n represents the number of columns in the garden (excluding the two start cells). The next two lines each contain n integers. The first of these lines represents the beauty values in the top row of the garden (from column 1 to column n), and the second line represents the beauty values in the bottom row.

Note: It is guaranteed that there is at least one valid path. You need to choose exactly one flower from each column, respecting the allowed moves, to maximize the harmony \(F\).

inputFormat

The first line contains four space‐separated integers: n, k, a, and b.

The next two lines each contain n space‐separated integers. The first of these lines represents the beauty values in the top row (columns 1 to n), and the second line represents the beauty values in the bottom row.

Example:

2 2 1 3
1 5
2 4

outputFormat

Output a single integer, the maximum possible harmony value \(F\) that can be achieved.

Example:

8

sample

2 2 1 3
1 5
2 4

8