风筝冲浪手 Nora 正在参加一场横跨弗里西亚群岛的比赛，这是一片位于荷兰北部、狭长且连绵的群岛。比赛在水面上进行，沿着从起点到终点的直线路径。航线上的任何岛屿都必须跳过去——不允许绕着岛屿冲浪。

比赛全长为 $s$ 米，群岛由起点和终点之间若干个互不相交的区间组成。在比赛过程中，Nora 可以通过两种不同的方式移动：

1. 如果两个点之间没有岛屿，Nora 可以以每秒 1 米的速度在两点之间冲浪。
2. 如果两个点之间的距离不超过 $d$ 米，且这两个点都不在岛屿上，Nora 可以在两点之间跳跃。无论跳跃距离多远，每次跳跃总是耗时 $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$ 行包含两个整数 $l_i$ 和 $r_i$ ($0 < l_i < r_i < s$ 且 $r_i - l_i \le d$)，给出第 $i$ 个岛屿相对于起点的边界（单位：米）。

岛屿之间互不接触，且按从左到右的顺序给出，即对于每个有效的 $i$，满足 $r_i < l_{i+1}$。

输出格式

输出一个数字，表示完成比赛所需的最短时间（单位：秒）。可以证明这个数字总是一个整数。

样例

输入 1

9 3 4
2
2 4
7 8

输出 1

11

输入 2

12 5 3
3
1 3
5 7
8 11

输出 2

9