24893번 - 캐슬 디펜스

성에 적들이 몰려오고 있다. 성은 수직선 상의 $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 100\,000,\ 1 \leq a,b,E \leq 10^8$)

$1+i(1\leq i\leq N)$번째 줄에는 $0$초인 시각에 좌표 $i$에 위치한 적들의 수 $A_i$가 주어진다. ($1 \leq i \leq N,\ 0 \leq A_i \leq 10^5$)

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