#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
void solve(){
int n,m;
cin>>n>>m;
vector<int> pos(m);
vector<int> pulo(m);
vector<int> cnt(n);
L(i,0,m-1){
cin>>pos[i]>>pulo[i];
cnt[pos[i]]++;
}
vector<vector<int>> amigos(n);
L(i,0,n-1){
if(cnt[i])amigos[i].reserve(cnt[i]);
}
L(i,0,m-1){
amigos[pos[i]].push_back(i);
}
L(i,0,n-1){
if(sz(amigos[i])>1){
sort(all(amigos[i]),[&](int a, int b){
return pulo[a]<pulo[b];
});
int pt= 0;
L(j,1,sz(amigos[i])-1){
if(pulo[amigos[i][j]]!=pulo[amigos[i][pt]]){
pt++;
amigos[i][pt]=amigos[i][j];
}
}
amigos[i].resize(pt+1);
}
}
const int MOD=1e9+7;
vector<int> dp(m,MOD);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
for(auto a:amigos[pos[0]]){
dp[a]=0;
pq.push({0,a});
}
vector<int> dpcasa(n+1,MOD);
dpcasa[pos[0]]=0;
if(!amigos[pos[0]].empty())amigos[pos[0]].clear();
while(!pq.empty()){//posso deletar os carinhas do amigo se tiver ruim
auto [d,v]=pq.top();
pq.pop();
if(v<0){
v++;
v=-v;
while(!amigos[v].empty()){
auto a=amigos[v].back();
amigos[v].pop_back();
dp[a]=d;
pq.push({dp[a],a});
}
continue;
}
if(d!=dp[v])continue;
if(v==1)break;
for(int i=1;pulo[v]*i+pos[v]<n;i++){
int casa=i*pulo[v]+pos[v];
if(dpcasa[casa]>dp[v]+i){
dpcasa[casa]=dp[v]+i;
if(!amigos[casa].empty())pq.push({dp[v]+i,-casa-1});
}
}
for(int i=1;pos[v]-pulo[v]*i>=0;i++){
int casa=pos[v]-i*pulo[v];
if(dpcasa[casa]>dp[v]+i){
if(!amigos[casa].empty())pq.push({dp[v]+i,-casa-1});
dpcasa[casa]=dp[v]+i;
}
}
}
cout<<((dp[1]==MOD)?-1:dp[1]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
solve();
}
