#include #include #include using namespace std; const int INF = 1 << 30; const int MAXL = 1000000; const int MAXN = 1000; int dp[MAXL + 1]; int has_cow[MAXL + 1]; int N, L, A, B; // If f(x) means the min cnt of sprinklers to cover [0...x], then we have // f(x) = INF, if x is odd // = INF, if x < 2A // = INF, if has_cow[x] // = 1, if 2A <= x <= 2B and !has_cow[x] // = min{f(y): x - 2B <= y <= x - 2A} + 1, if 2B < x and !has_cow[y] struct Fx { int x; int f; Fx(int x = 0, int f = 0) : x(x), f(f) {} bool operator<(const Fx &that) const { return this->f > that.f; } }; int main() { scanf("%d %d %d %d", &N, &L, &A, &B); A <<= 1, B <<= 1; for (int i = 0; i < N; i++) { int s, e; scanf("%d %d", &s, &e); has_cow[s + 1]++; has_cow[e]--; } for (int i = 0, cows = 0; i <= L; i++) { dp[i] = INF; cows += has_cow[i]; has_cow[i] = 0 < cows; } priority_queue pq; for (int x = A; x <= B; x += 2) { if (!has_cow[x]) { dp[x] = 1; // Ensure that for each x, the y in pq has y <= x - A if (x <= B + 2 - A) pq.push(Fx{x, 1}); } } for (int x = B + 2; x <= L; x += 2) { if (!has_cow[x]) { Fx fx; while (!pq.empty()) { fx = pq.top(); if (fx.x < x - B) pq.pop(); else break; } if (!pq.empty()) dp[x] = fx.f + 1; } // Push next Fx to queue. if (dp[x + 2 - A] != INF) pq.push(Fx(x + 2 - A, dp[x + 2 - A])); } int cnt = dp[L] == INF ? -1 : dp[L]; printf("%d\n", cnt); return 0; }