#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pp;
int N,M;
int a[30010],P[30010];
int dist[30010];
bool chk[30010];
priority_queue<pp,vector<pp>,greater<pp> > Q;
int main(){
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++){
scanf("%d%d",&a[i],&P[i]);
}
memset(dist,0x3f,sizeof(dist));
int INF=dist[0];
dist[1]=0;
Q.push(pp(0,1));
int v;
while(!Q.empty()){
do{
v=Q.top().second;Q.pop();
}while(!Q.empty()&&chk[v]);
chk[v]=1;
if(v==0)break;
for(int i=0;i<M;i++){
if(abs(a[v]-a[i])%P[i]==0){
if(dist[i]>dist[v]+abs(a[v]-a[i])/P[i]){
dist[i]=dist[v]+abs(a[v]-a[i])/P[i];
Q.push(pp(dist[i],i));
}
}
}
}
if(dist[0]==INF){
puts("-1");
}else{
printf("%d",dist[0]);
}
}
