P17009 [NWERC 2019] 风筝冲浪 / Kitesurfing

译自 [Northwestern Europe Regional Contest (NWERC) 2019](http://2019.nwerc.eu)。

风筝冲浪者 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

输出一个数，表示完成比赛所需的最短时间，单位为秒。 可以证明该数一定是整数。

【数据规模与约定】 - $1\le s,d,t\le 10^9$。 - $0\le n\le 500$。 - $0