캐슬 디펜스

성에 적들이 몰려오고 있다. 성은 수직선 위 $0$ 지점에 있고, 적들은 $1$ 이상 $N$ 이하의 정수 좌표에 있다.

적들은 $1$초마다 성이 있는 방향으로 $1$만큼 전진한다. 성에 도달한 적은 성에 $1$의 대미지를 주고 소멸한다.

성은 $E$만큼의 대미지를 입는 순간 파괴된다.

세윤이는 성을 지키기 위해 $k$명($0 \leq k$)의 궁수를 고용하기로 했다. 궁수는 $t$초($1 \leq t \leq 10^9$)마다 한 명의 적에게 화살을 쏠 수 있고, 화살에 맞은 적은 소멸한다. 궁수들은 성이 파괴되지 않도록 최선의 전략으로 화살을 쏜다.

궁수들은 정확히 $0.5$초, $t+0.5$초, $2t+0.5$초… 시점에 화살을 쏠 수 있고, 적들은 정확히 $1$초, $2$초, $3$초… 시점에 이동한다.

성이 파괴되지 않는 정수 $k$와 $t$에 대하여 $a\cdot k-b\cdot t$의 최솟값을 구하여라.

첫째 줄에 네 정수 $N$, $a$, $b$, $E$가 주어진다 ($1 \leq N \leq 100000$, $1 \leq a, b, E \leq 10^8$).

$(1+i)$번째 줄($1 \leq i \leq N$)에는 $0$초일 때 좌표 $i$에 있는 적의 수 $A_i$가 주어진다 ($0 \leq A_i \leq 10^5$).

성이 파괴되지 않는 정수 $k$와 $t$의 모든 경우에 대하여 $a\cdot k-b\cdot t$의 최솟값을 출력한다.