K. Kitesurfing
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Illustration of the two sample cases.

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

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 \lt \ell_i \lt r_i \lt 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 \lt \ell_{i+1}$$$ for each valid $$$i$$$.

Output

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.

Examples
Input
9 3 4
2
2 4
7 8
Output
11
Input
12 5 3
3
1 3
5 7
8 11
Output
9