#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5; // twice the contraints (since we duplicate intervals in modifyIntervals())
const int MAXK = 21; // ~log(MAXN), for binary lifting
long long n, m;
long long s[MAXN], e[MAXN];
int nextBest[MAXN]; // precalculated next best interval
int lift[MAXN][MAXK]; // precalculated binary lifting. lift[i][k] is taking 2^k intervals, starting from i-th one
void readInput() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> s[i] >> e[i];
}
}
void removeUnnecessaryIntervals() {
// interval is unnecessary if it is covered fully by other intervals
int cnt = 0;
// sort the intervals
vector<pair<long long, long long>> intervals;
for (int i = 0; i < n; i++)
intervals.push_back({s[i], -e[i]}); // this will help sort by increasing s[i],
// and then by decreasing e[i]
sort(intervals.begin(), intervals.end());
long long furthestEnd = -1;
for (auto interval : intervals) {
long long start = interval.first;
long long end = -interval.second;
if (end <= furthestEnd) {
continue; // this interval is unnecessary
}
furthestEnd = end;
s[cnt] = start;
e[cnt] = end;
cnt++;
}
n = cnt; // update interval count
}
void modifyIntervals() {
// to make implementation a bit easier
// deal with the cases of s > e
for (int i = 0; i < n; i++) {
if (s[i] > e[i]) e[i] += m;
}
// duplicate all intervals: (s, e) -> (s+m, e+m)
for (int i = 0; i < n; i++) {
s[i+n] = s[i] + m;
e[i+n] = e[i] + m;
}
n *= 2; // since we duplicated
removeUnnecessaryIntervals(); // remove covered fully by other intervals
}
void precalcNexts() {
// sort intervals by their starts
vector<pair<long long, int>> intervals; // vector of pairs {start, id}
for (int i = 0; i < n; i++)
intervals.push_back({s[i], i});
sort(intervals.begin(), intervals.end());
// calculate nexts with two pointers technique
int i = 0;
for (auto interval : intervals) {
int id = interval.second;
while (i < n) {
int intervalId = intervals[i].second;
if (s[intervalId] > e[id]) // not overlapping
break;
i++;
}
nextBest[id] = intervals[i - 1].second;
}
}
void precalcBinaryLifting() {
for (int i = 0; i < n; i++)
lift[i][0] = nextBest[i];
for (int k = 1; k < MAXK; k++) for (int i = 0; i < n; i++)
lift[i][k] = lift[ lift[i][k-1] ][k-1];
}
int tryFrom(int startAdmin) {
long long startTime = s[startAdmin];
// do binary lifting (binary search) to find the furthest reachable admin
// such that it would still not cover full circle
int cntJumps = 0;
int curAdmin = startAdmin;
for (int i = MAXK-1; i >= 0; i--) {
int jumpedToId = lift[curAdmin][i];
if (e[jumpedToId] < (startTime + m)) { // does not cover full circle
cntJumps += (1<<i); // 2^i
curAdmin = jumpedToId;
}
}
// we found the last before we get to full circle
cntJumps++;
curAdmin = lift[curAdmin][0];
if (e[curAdmin] < (startTime + m)) {
return -1; // impossible since we did not cover full circle
}
return cntJumps + 1;
}
int main() {
readInput();
modifyIntervals(); // see the explanation at the top
precalcNexts();
precalcBinaryLifting();
int ans = -1;
for (int i = 0; i < n; i++) {
int curTaken = tryFrom(i);
// update ans
if (curTaken == -1) continue;
if (ans == -1 || curTaken < ans) ans = curTaken;
}
cout << ans << endl;
return 0;
}
