背景

译自 Northwestern Europe Regional Contest (NWERC) 2019。

题目描述

风筝冲浪者 Nora 正参加一场穿越弗里斯兰群岛的比赛。这是一片位于荷兰北部、非常狭长的群岛。比赛在水面上进行，路线是从起点到终点的一条直线。路线上的任何岛屿都必须跳过去，不允许绕行。

比赛全长 $s$ 米，群岛由起点和终点之间若干互不相交的区间组成。比赛中，Nora 有两种移动方式：

1. 她可以在任意两个点之间以每秒 $1$ 米的速度冲浪，前提是两点之间没有岛屿。
2. 如果两个点之间的距离不超过 $d$ 米，且两个点都不在岛上，她可以在它们之间跳跃。一次跳跃总是花费 $t$ 秒，与跳跃距离无关。

虽然不能降落在岛上，也不能冲浪穿过岛屿，但允许经过任何岛屿的端点。

:::align{center}

:::

你的任务是求 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}$。

输出格式

输出一个数，表示完成比赛所需的最短时间，单位为秒。

可以证明该数一定是整数。

9 3 4
2
2 4
7 8

11

12 5 3
3
1 3
5 7
8 11

9

提示

【数据规模与约定】

• $1\le s,d,t\le 10^9$。
• $0\le n\le 500$。
• $0<\ell_i<r_i<s$，且 $r_i-\ell_i\le d$。
• 岛屿互不接触，并按从左到右顺序给出，即 $r_i<\ell_{i+1}$。
• 保证比赛总是可以完成。
• 可以证明最短时间一定是整数。