Barbara 有一个花园。花园长而窄，被划分为 $m$ 个大小相同的区域，排成一排。她的朋友 Babara 送给她 $n$ 块石板作为生日礼物。Barbara 随后将这些石板放置在她的花园中，这样她每天都可以享受在石板之间跨步的乐趣。第 $i$ 块石板完全占据了花园的第 $l_i$ 到第 $r_i$ 个区域。石板之间互不重叠，且任意两块石板之间至少有 $d$ 个空区域。

下图是当 $m = 15$，$n = 3$，$d = 2$ 且三块石板分别占据区域 2–4、7–7、12–13 时的有效放置方案。

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

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

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

输入格式

第一行包含四个整数 $n$、$m$、$d$ 和 $x$。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $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$
• 对于 $i \in \{1, 2, \dots, n\}$，有 $1 \le l_i \le r_i \le m$
• 对于 $i \in \{1, 2, \dots, n - 1\}$，有 $r_i + d + 1 \le l_{i+1}$。即石板按从左到右的顺序给出。

样例

样例输入 1

3 15 2 3
2 4
7 7
12 13

样例输出 1

4

样例输入 2

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

样例输出 2

9

样例输入 3

1 100 99 1
1 1

样例输出 3

-1