타이어 패치

카를로스는 환경 문제에 관심이 많아서 되도록 오염이 적은 교통수단을 쓴다. 최근에 집 근처로 직장을 옮겼고, 지금은 자전거로 출근한다.

문제는 집과 직장 사이의 길에 못 공장이 있다는 것이다. 트럭에서 못이 떨어지는 일이 잦고, 떨어진 못이 카를로스의 자전거 타이어를 찌른다. 그래서 카를로스는 타이어에 패치를 여러 장 붙여야 한다.

패치는 두 종류다. 두 종류 모두 폭은 타이어 폭과 같고 길이만 다르다. 패치 값은 길이에 비례하므로, 카를로스는 패치를 자르지 않은 채로 쓰면서 붙이는 패치의 길이 합을 가장 작게 만들려고 한다.

수리는 타이어의 한 지점에 분필로 표시를 남기고, 그 표시에서 시계 방향으로 각 구멍까지의 거리를 적는 것으로 시작한다. 구멍은 하나도 빠짐없이 패치 한 장에 완전히 덮여야 한다. 패치는 타이어 둘레의 어느 위치에나 붙일 수 있고, 두 종류를 각각 몇 장이든 쓸 수 있으며, 패치끼리 겹쳐도 된다. 구멍의 위치가 주어졌을 때 가장 값이 싼 수리 방법을 구하라.

첫째 줄에 정수 네 개 $N$, $C$, $T_1$, $T_2$가 주어진다. $N$은 타이어에 난 구멍의 개수이고, $C$는 타이어의 둘레 길이다. $T_1$과 $T_2$는 두 패치의 길이다. 길이는 모두 센티미터 단위다. 둘째 줄에 정수 $N$개 $F_1, F_2, \dots, F_N$이 주어진다. $F_i$는 분필 표시에서 시계 방향으로 구멍 $i$까지의 거리다.

제한

• $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$)
• 두 구멍 사이의 거리가 정확히 $k$ 센티미터면, 길이가 $k$ 센티미터인 패치 한 장이 두 구멍을 함께 덮는다.
• 서로 다른 구멍이 같은 위치에 있을 수도 있다.

모든 구멍을 덮는 데 필요한 패치 길이 합의 최솟값을 정수 하나로 한 줄에 출력한다.