说明

芭芭拉有一座花园。花园狭长，被划分成 $m$ 个大小相等的区域，排成一行。她的朋友芭芭拉送给她 $n$ 块石板作为生日礼物。芭芭拉将这些石板放置在花园中，这样她每天就可以从一块石板跳到另一块石板上享受乐趣。第 $i$ 块石板完全占据花园的第 $l_i$ 个到第 $r_i$ 个区域。这些石板互不重叠，且任意两块石板之间至少有 $d$ 个空区域。

下面是一个有效的石板放置示例，其中 $m = 15$，$n = 3$，$d = 2$，三块石板分别占据区域 $2–4$、$7–7$ 和 $12–13$。

:::align{center} :::

芭芭拉最近又买了一块新石板，它将占据花园中连续的 $x$ 个区域。她将移动原有的石板，然后将新石板放置在花园中的某个位置。在移动原有石板并放置新石板之后，石板之间不能重叠，且任意两块石板之间必须至少有 $d$ 个空区域。在 石板移动过程中，石板之间可以暂时重叠。

请注意，在移动石板的过程中，两块石板之间可以少于 $d$ 个空区域。例如，当 $d = 2$ 时，以下过程是有效的：

:::align{center} :::

将一块石板移动到一个相邻区域需要花费一分钟。例如，上述重新排列过程需要 $4$ 分钟。现在芭芭拉想知道重新排列石板所需的最小总时间，以便她能节省时间用于“其他目的”。

输入格式

第一行包含四个整数 $n$、$m$、$d$ 和 $x$。接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$。

输出格式

输出重新排列石板所需的最小总时间（以分钟为单位），使得新石板能够被放置在花园中。如果无论如何重新排列石板，新石板都无法放置在花园中，则输出 $-1$。

3 15 2 3
2 4
7 7
12 13

4

5 100 1 75
2 3
5 7
11 13
17 19
23 29

9

1 100 99 1
1 1

-1

提示

• $1 \le n \le 2000$
• $1 \le d \le m \le 10^9$
• $1 \le x \le m \le 10^9$
• $1 \le l_i \le r_i \le m$，对于 $i \in \{1, 2, \dots, n\}$
• $r_i + d + 1 \le l_{i+1}$，对于 $i \in \{1, 2, \dots, n - 1\}$，即石板按从左到右的顺序给出。

翻译由 DeepSeek V3.2 完成