#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct data{
int to,dist;
};
struct cmp{
bool operator()(data d1,data d2){
return d1.dist>d2.dist;
}
};
int n,m;
int dist[30010];
data arr[30010];
bool visit[30010];
vector<data> vt[30010];
priority_queue<data,vector<data>,cmp> pq;
void dij(int a){
int i;
data s;
pq.push((data){a,1});
while(!pq.empty()){
a=pq.top().to; pq.pop();
if(visit[a]) continue; visit[a]=1;
for(i=0;i<vt[a].size();i++){
s=vt[a][i];
if(dist[s.to]==0 || dist[s.to]>dist[a]+s.dist){
pq.push((data){s.to,dist[a]+s.dist}); dist[s.to]=dist[a]+s.dist;
}
}
}
}
int main(){
int i,j;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++) scanf("%d %d",&arr[i].to,&arr[i].dist);
for(i=0;i<m;i++){
for(j=i+1;j<m;j++){
if(!(abs(arr[i].to-arr[j].to)%arr[i].dist)) vt[i].push_back((data){j,abs(arr[i].to-arr[j].to)/arr[i].dist});
if(!(abs(arr[i].to-arr[j].to)%arr[j].dist)) vt[j].push_back((data){i,abs(arr[i].to-arr[j].to)/arr[j].dist});
}
}
dist[0]=1;
dij(0);
if(!visit[1]) printf("-1");
else printf("%d",dist[1]-1);
return 0;
}
