효율적인 슬랩스톤 재배치

Barbara의 정원은 길고 좁으며, 한 줄로 늘어선 $m$개의 같은 크기 구역으로 나뉘어 있다. 친구 Babara가 생일 선물로 슬랩스톤 $n$개를 주었다. Barbara는 이 슬랩스톤을 정원에 놓고 매일 돌에서 돌로 건너다니며 즐긴다. $i$번째 슬랩스톤은 $l_i$번째 구역부터 $r_i$번째 구역까지를 빈틈없이 차지한다. 슬랩스톤끼리는 겹치지 않으며, 어떤 두 슬랩스톤 사이에든 최소 $d$개의 빈 구역이 있다.

Barbara가 최근 연속된 $x$개의 구역을 차지하는 슬랩스톤을 하나 더 샀다. 그녀는 기존 슬랩스톤을 정원 안에서 옮긴 뒤 새 슬랩스톤을 정원 어딘가에 놓는다. 이동 후 슬랩스톤은 서로 겹치지 않아야 하며, 어떤 두 슬랩스톤 사이에도 최소 $d$개의 빈 구역이 있어야 한다. 재배치하는 도중에도 슬랩스톤은 겹치면 안 된다.

슬랩스톤 하나를 인접한 구역으로 옮기는 데 1분이 걸린다. 예를 들어 위 과정은 4분이 걸린다. Barbara는 다른 일에 시간을 쓸 수 있도록 슬랩스톤을 재배치하는 데 드는 총 시간의 최소값을 알고 싶어 한다.

첫 줄에 정수 $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$
• $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}$. 슬랩스톤은 왼쪽에서 오른쪽 순서로 주어진다.