#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;
int d(int x,int y,vector<vector<pair<int,int> > >&s){
int N=s.size();
vector<int>dis(N,1e9);
dis[x]=0;
priority_queue<pair<int,int> >pq;
pq.push(make_pair(0,x));
while(!pq.empty()){
int nodo=pq.top().second;
int d=-pq.top().first;
pq.pop();
if(d>dis[nodo])
continue;
dis[nodo]=d;
for(pair<int,int>v:s[nodo]){
int vec=v.first;
int dv=v.second;
if(dis[vec]>dis[nodo]+dv){
dis[vec]=dis[nodo]+dv;
pq.push(make_pair(-dis[vec],vec));
}
}
}
if(dis[y]==1e9){
return -1;
}
else{
return dis[y];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N,M,B,P;
cin>>N>>M;
vector<vector<pair<int,int> > >s(N);
vector<int>b(M);
for(int i=0;i<M;i++){
cin>>B>>P;
b[i]=B;
int j=B;
int o=1,u=1;
while(j-P>=0){
s[B].push_back(make_pair(j-P,P*o));
j=j-P;
o++;
}
while(j+P<=N){
s[B].push_back(make_pair(j+P,P*u));
j=j+P;
u++;
}
}
int x=b[0];
int y=b[1];
cout<<d(x,y,s);
return 0;
}
