#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define maxn 30005
struct node {
int x,val;
node(int _x = 0,int _val = 0) {
x = _x; val = _val;
}
bool operator < (node a) const {
return a.val<val;
}
};
int n,m,st,ft;
int mem[maxn];
int last[maxn];
bool ok[175][maxn];
vector<pair<int,int> > from[maxn];
priority_queue<node> heap;
main() {
int i,j,x,y,pos,val,cnt;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++) {
scanf("%d%d",&pos,&val);
if(i==0) st = pos;
if(i==1) ft = pos;
if(val>sqrt(n)) {
x = pos; cnt = 0;
while(x<n) {
from[pos].push_back({x,cnt});
// printf("1) %d -> %d (%d)\n",pos,x,cnt);
x += val; cnt++;
}
x = pos; cnt = 0;
while(x>=0) {
from[pos].push_back({x,cnt});
// printf("1) %d -> %d (%d)\n",pos,x,cnt);
x -= val; cnt++;
}
}
else ok[val][pos] = 1;
}
for(i=1;i<=sqrt(n);i++) {
memset(last,-1,sizeof(last));
for(x=0;x<n;x++) {
if(last[x%i]!=-1) {
from[last[x%i]].push_back({x,(x-last[x%i])/i});
// printf("2) %d -> %d (%d)\n",last[x%i],x,(x-last[x%i])/i);
}
if(ok[i][x]) last[x%i] = x;
}
memset(last,-1,sizeof(last));
for(x=n-1;x>=0;x--) {
if(last[x%i]!=-1) {
from[last[x%i]].push_back({x,(last[x%i]-x)/i});
// printf("2) %d -> %d (%d)\n",last[x%i],x,(last[x%i]-x)/i);
}
if(ok[i][x]) last[x%i] = x;
}
}
for(i=0;i<n;i++) mem[i] = inf;
mem[st] = 0;
heap.push(node(st,0));
while(!heap.empty()) {
x = heap.top().x; val = heap.top().val; heap.pop();
// printf("%d : %d\n",x,val);
if(val!=mem[x]) continue;
for(i=0;i<from[x].size();i++) {
y = from[x][i].first; val = from[x][i].second;
if(mem[y] > mem[x] + val) {
mem[y] = mem[x] + val;
heap.push(node(y,mem[y]));
}
}
}
if(mem[ft]==inf) printf("-1");
else printf("%d",mem[ft]);
}
