#include <bits/stdc++.h>
#define ll long long
#define task "FIRE"
using namespace std;
const int N = 1e6 + 16;
const ll INF = 1e18;
int n, m;
ll s[N], e[N];
namespace sub3 {
ll cnt, result = INF;
pair <ll, ll> a[N];
vector < pair <ll, ll> > checkLines;
bool cmp(pair <ll, ll> a, pair <ll, ll> b) {
if (a.first == b.first) {
return a.second > b.second;
}
return a.first < b.first;
}
ll query(pair <ll, ll> target) {
ll curP = 1, p = target.first, cnt = 0;
while (p <= target.second) {
ll r = -1;
while (curP <= n && a[curP].first <= p) {
r = max(a[curP].second, r);
curP++;
}
if (r < p) {
return -1;
}
p = r + 1;
cnt++;
}
return cnt;
}
void solve() {
checkLines.push_back({0, m - 1});
for (int i = 1; i <= n; i++) {
if (s[i] > e[i]) {
checkLines.push_back({e[i], e[i] + m - 1});
e[i] += m;
}
a[i] = {s[i], e[i] - 1};
}
sort(a + 1, a + 1 + n, cmp);
for (auto x : checkLines) {
ll ans = query(x);
if (ans == -1) {
continue;
}
result = min(result, ans);
}
if (result == INF) {
result = -1;
}
cout << result;
}
}
namespace sub6 {
ll result = INF;
pair<ll,ll> a[N];
vector<pair<ll,ll>> checkLines;
int maxx = 0;
const int LOG = 22; // đủ cho up to ~4M
void compress() {
vector<ll> c;
for (int i = 1; i <= n; i++) {
c.push_back(a[i].first);
c.push_back(a[i].second);
}
for (auto x : checkLines) {
c.push_back(x.first);
c.push_back(x.second);
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
for (int i = 1; i <= n; i++) {
a[i].first = lower_bound(c.begin(), c.end(), a[i].first) - c.begin() + 1;
a[i].second = lower_bound(c.begin(), c.end(), a[i].second) - c.begin() + 1;
maxx = max(maxx, (int)a[i].first);
maxx = max(maxx, (int)a[i].second);
}
for (auto &x : checkLines) {
x.first = lower_bound(c.begin(), c.end(), x.first) - c.begin() + 1;
x.second = lower_bound(c.begin(), c.end(), x.second) - c.begin() + 1;
maxx = max(maxx, (int)x.first);
maxx = max(maxx, (int)x.second);
}
}
static int maxR_idx[N];
static int up[N][LOG];
void solve() {
checkLines.clear();
checkLines.push_back({0, m - 1});
for (int i = 1; i <= n; i++) {
if (s[i] > e[i]) {
checkLines.push_back({e[i], e[i] + m - 1});
e[i] += m;
}
a[i] = {s[i], e[i] - 1};
}
compress();
// reset arrays up to maxx+1
for (int i = 0; i <= maxx + 1; i++) {
maxR_idx[i] = 0;
for (int j = 0; j < LOG; j++) up[i][j] = maxx + 1;
}
// maxR_idx[pos] = furthest right index reachable when starting at position pos
for (int i = 1; i <= n; i++) {
int L = (int)a[i].first;
int R = (int)a[i].second;
maxR_idx[L] = max(maxR_idx[L], R);
}
// prefix max so maxR_idx[i] = best reachable from any interval that starts <= i
for (int i = 1; i <= maxx; i++) {
maxR_idx[i] = max(maxR_idx[i - 1], maxR_idx[i]);
}
// define next position after taking one interval starting at pos:
// nxt[pos] = maxR_idx[pos] + 1 (if maxR_idx[pos] < pos then impossible from pos)
for (int i = 1; i <= maxx; i++) {
up[i][0] = min(maxx + 1, maxR_idx[i] + 1);
}
up[maxx + 1][0] = maxx + 1; // sentinel
// build binary lifting table
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= maxx + 1; i++) {
up[i][j] = up[ up[i][j - 1] ][ j - 1 ];
}
}
// answer queries for each check line
for (auto x : checkLines) {
int u = (int)x.first, v = (int)x.second;
if (u < 1 || v < 1 || u > maxx || v > maxx) {
// if compressed indices out of range skip (shouldn't happen)
}
if (u > v) continue;
// if even the best coverage from u doesn't reach u, impossible
if (maxR_idx[u] < u) continue;
int pos = u;
int ans = 0;
// jump as much as possible while still <= v
for (int j = LOG - 1; j >= 0; j--) {
if (up[pos][j] <= v) {
pos = up[pos][j];
ans += (1 << j);
}
}
// after jumps, if pos <= v we still need one more interval
if (pos <= v) ans++;
result = min(result, 1LL * ans);
}
if (result == INF) result = -1;
cout << result;
}
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i] >> e[i];
}
if (n <= 5000) {
sub3 :: solve();
}
else {
sub6 :: solve();
}
return 0;
}
