P15909 [TOPC 2024] Efficient Slabstones Rearrangement

芭芭拉有一座花园。花园狭长，被划分成 $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$。

- $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 完成