#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
int N, M, st=0, ed=0;
cin>>N>>M;
vector<vector<int>> A(N);
for(int i=0; i<N; i++) {
int x, m;
cin>>x>>m;
if(i==0) st=x;
else if(i==1) ed=x;
A[x].push_back(m);
}
for(auto&v:A) {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
}
vector<int> D(N, INT_MAX);
vector<vector<int>> Q(N+1);
int qs=1, k=0, n=0;
Q[0].push_back(st); D[st]=0;
while(qs) {
for(int x:Q[k]) if(D[x]==n) {
if(x==ed) { cout<<n; return 0; }
for(int m:A[x]) {
for(int i=x+m, j=k+1, d=D[x]+1; i<N; i+=m, j=j+1-(j==N)*(N+1), d++) {
if(d<D[i]) D[i]=d, Q[j].push_back(i), qs++;
if(binary_search(rbegin(A[i]), rend(A[i]), m)) break;
}
for(int i=x-m, j=k+1, d=D[x]+1; i>=0; i-=m, j=j+1-(j==N)*(N+1), d++) {
if(d<D[i]) D[i]=d, Q[j].push_back(i), qs++;
if(binary_search(rbegin(A[i]), rend(A[i]), m)) break;
}
}
}
qs-=Q[k].size();
Q[k].clear();
k=k+1-(k==N)*(N+1);
++n;
}
cout<<-1;
}
