Tire Patches

Carlos cares about the environment, so he takes the least polluting transport he can. He recently took a job close to home and now rides his bike to work.

The trouble is that the road between his home and his job passes a nail factory. Nails fall off the trucks often, and they puncture the tires of Carlos' bike. He therefore has to put several patches on those tires.

Carlos uses two types of patch. Both are as wide as the tire and differ only in length. The price of a patch is proportional to its length, so Carlos wants the total length of the patches he uses to be as small as possible, and he never cuts a patch.

A repair starts with a chalk mark at one point of the tire. Carlos then writes down the distance from that mark to each hole, measured clockwise. Every hole must be completely covered by one patch. A patch can be placed anywhere along the tire, either type can be used any number of times, and patches may overlap. Given the positions of the holes, find the cheapest repair.

The first line contains four integers $N$, $C$, $T_1$ and $T_2$. Here $N$ is the number of holes in the tire and $C$ is the length of the tire's circumference. The lengths of the two patches are $T_1$ and $T_2$. All lengths are in centimetres. The second line contains $N$ integers $F_1, F_2, \dots, F_N$, where $F_i$ is the distance from the chalk mark to hole $i$ measured clockwise.

Restrictions

• $1 \le N \le 1000$
• $1 \le C \le 10^6$
• $1 \le T_1, T_2 \le C$
• $0 \le F_i \le C - 1$ ($1 \le i \le N$)
• If the distance between two holes is exactly $k$ centimetres, one patch of length $k$ centimetres covers both holes.
• Two different holes may sit at the same position.

Print a single line with one integer, the smallest total length of patches needed to cover every hole.