Tycho

행성 탐사 차량 Tycho VIII는 광물 샘플을 채취한 뒤 본부 기지로 돌아가야 한다. Tycho는 위치 $0$에서 기지가 있는 위치 $b$까지 직선으로 이동한다. 이동하는 동안 초당 $1$의 속도로 느리지만 일정하게 전진한다. 매초 혹독한 행성 환경으로 인해 $1$의 환경 피해를 입는다.

인근 펄서에서 나오는 방사선은 $p$초마다 $d$의 피해를 추가로 준다. 다만 이동 경로 중 $n$곳의 은신처(동굴, 식생, 큰 바위, 행성 거대 동물의 사체 등) 중 한 곳에 숨으면 방사선 피해를 피할 수 있다. Tycho는 경로 위 어느 지점에서든 정수 초 동안 멈춰 있을 수 있다.

출발 지점 $0$과 기지 $b$는 모두 은신처이므로, 그곳에서는 방사선 피해를 입지 않는다.

기지가 위치 $18$에 있고 은신처가 위치 $8$과 $15$에 있는 경우를 생각해 보자.

펄서의 주기가 $4$라고 하자. 은신처가 없는 Tycho는 시각 $4$, $8$, $12$ 등에 피해를 입는다. Tycho가 시각 $0$에 (은신처인) 출발 지점을 떠나면 $8$초 뒤 첫 번째 은신처에 도착하고, 시각 $4$에 방사선 피해 $d$를 입는다. 시각 $8$에는 은신처에 있으므로 피해가 없다. 멈추지 않고 계속 가면 시각 $18$에 기지에 도착하며, 그 사이 시각 $12$와 $16$에 $d$씩 두 번 더 피해를 입는다. 결과적으로 방사선 피해는 $3d$, 환경 피해는 $18$이다.

반대로 Tycho가 두 번째 은신처(위치 $15$)에서 $1$초 기다리면 시각 $16$의 펄스가 피해를 주지 않고, 시각 $19$에 기지에 도착한다. 총 피해는 $2d + 19$이다. 대부분의 $d$ 값에서는 이 방법이 더 낫다. 두 경우는 다음과 같다.

펄서의 주기가 $10$이라면 Tycho는 출발 지점에서 $2$초 기다린 뒤, 어떤 은신처에도 멈추지 않고 곧장 기지로 갈 수 있다. 첫 번째 은신처(위치 $8$)를 펄서가 펄스를 내보내는 순간에 정확히 지나가고, 시각 $20$에 기지에 도착한다. 환경 피해는 $20$이고 방사선 피해는 전혀 없다.

첫째 줄에 기지의 위치 $b$, 펄서의 펄스 주기 $p$, 펄스마다 추가되는 방사선 피해 $d$, 은신처의 개수 $n$이 공백으로 구분되어 주어진다. 이어서 $n$개의 줄에 은신처의 위치 $a_1, \ldots, a_n$이 한 줄에 하나씩 주어진다.

Tycho가 $b$에 도착하기까지 받는 최소 피해량의 합을 정수 하나로 출력한다.

$p < b$와 $n < b$라고 가정해도 된다. 항상 $1 \le b \le 10^{12}$, $0 \le d \le 10^6$, $0 \le n \le 10^5$이다. 은신처 위치는 $0 < a_1 < \cdots < a_n < b$를 만족한다.