카이트서핑

카이트서퍼 Nora는 네덜란드 북부의 길고 가느다란 군도인 프리지언 제도를 가로지르는 경주에 참가한다. 경주는 물 위에서 열리며 출발점에서 결승점까지 직선으로 진행된다. 경로 위의 섬은 반드시 뛰어넘어야 하며, 섬을 돌아서 서핑하는 것은 허용되지 않는다.

경주의 길이는 $s$미터이며, 군도는 출발선과 결승선 사이에 서로 겹치지 않는 여러 구간으로 이루어진다. 경주 중 Nora는 다음 두 가지 방법으로 움직일 수 있다.

1. 두 점 사이에 섬이 없다면, 두 점 사이를 초속 1미터로 서핑할 수 있다.
2. 두 점의 거리가 $d$미터 이하이고 두 점 모두 섬 위에 있지 않다면, 두 점 사이를 점프할 수 있다. 점프는 이동 거리와 관계없이 항상 $t$초가 걸린다.

섬 위에 착지하거나 섬을 가로질러 서핑할 수는 없지만, 섬의 끝점을 방문하는 것은 허용된다.

그림 K.1: 두 예제 케이스 설명도.

Nora가 경주를 마치는 데 걸리는 최단 시간을 구하라. 어떤 섬도 길이가 $d$미터를 넘지 않는다고 가정해도 된다. 즉, 경주를 끝내는 것은 항상 가능하다.

입력은 다음과 같이 구성된다.

• 첫 줄에 세 정수 $s$, $d$, $t$가 주어진다 ($1 \le s, d, t \le 10^9$). $s$는 경주의 길이(미터), $d$는 최대 점프 거리(미터), $t$는 점프 한 번에 걸리는 시간(초)이다.
• 다음 줄에 섬의 개수 $n$이 주어진다 ($0 \le n \le 500$).
• 이어서 $n$줄이 주어지며, $i$번째 줄에는 두 정수 $\ell_i$와 $r_i$가 주어진다 ($0 < \ell_i < r_i < s$이고 $r_i - \ell_i \le d$). 출발점으로부터의 거리로 나타낸 $i$번째 섬의 경계이다.

섬끼리는 서로 닿지 않으며 왼쪽에서 오른쪽 순서로 주어진다. 즉, 유효한 모든 $i$에 대해 $r_i < \ell_{i+1}$이다.

Nora가 경주를 마치는 데 필요한 최단 시간(초)을 정수 하나로 출력하라. 이 값은 항상 정수로 나타낼 수 있다.