Problem Description

Nora the kitesurfer is taking part in a race across the Frisian islands, a very long and thin archipelago in the north of the Netherlands. The race takes place on the water and follows a straight line from start to finish. Any islands on the route must be jumped over – it is not allowed to surf around them.

The length of the race is $s$ metres and the archipelago consists of a number of non-intersecting intervals between start and finish line. During the race, Nora can move in two different ways:

1. Nora can surf between any two points at a speed of $1$ metre per second, provided there are no islands between them.

2. Nora can jump between any two points if they are at most $d$ metres apart and neither of them is on an island. A jump always takes $t$ seconds, regardless of distance covered.

While it is not possible to land on or surf across the islands, it is still allowed to visit the end points of any island.

:::align{center} :::

Your task is to find the shortest possible time Nora can complete the race in. You may assume that no island is more than $d$ metres long. In other words it is always possible to finish the race.

Input Format

The input consists of:

• One line with three integers $s,d$ and $t$ ($1 \le s,d,t \le 10^9$), where $s$ is the length of the race in metres, $d$ is the maximal jump distance in metres, and $t$ is the time needed for each jump in seconds.

• One line with an integer $n$ ($0 \le n \le 500$), the number of islands.

• $n$ lines, the $i$th of which contains two integers $\ell_i$ and $r_i$ ($0 < \ell_i < r_i < s$ and $r_i-\ell_i \le d$), giving the boundaries of the $i$th island in metres, relative to the starting point.

The islands do not touch and are given from left to right, that is $r_i < \ell_{i+1}$ for each valid $i$.

Output Format

Output one number, the shortest possible time in seconds needed to complete the race. It can be shown that this number is always an integer.

9 3 4
2
2 4
7 8

11

12 5 3
3
1 3
5 7
8 11

9