#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int maxn=3e4+5;
const int B = 110;
int n,m;
int b[maxn],p[maxn];
int ver[maxn][B];
int dis[maxn * B];
bool vis[maxn * B];
vector<pair<int,int>>E[maxn * B];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int sq = 100;
int sz = n - 1;
for(int i = 0;i < n;i++) for(int j = 1;j <= sq;j++) ver[i][j] = ++sz;
for(int i = 0;i < n;i++){
for(int j = 1;j <= sq;j++){
E[ver[i][j]].push_back({i,0});
// E[i].push_back({ver[i][j],0});
if(i - j >= 0) E[ver[i][j]].push_back({ver[i-j][j],1});
if(i + j < n) E[ver[i][j]].push_back({ver[i+j][j],1});
}
}
for(int i = 0;i < m;i++){
cin >> b[i] >> p[i];
if(p[i] <= sq) E[b[i]].push_back({ver[b[i]][p[i]],0});
else {
for(int j = 1;b[i] - j * p[i] >= 0;j++) E[b[i]].push_back({b[i] - j * p[i],j});
for(int j = 1;b[i] + j * p[i] < n;j++) E[b[i]].push_back({b[i] + j * p[i],j});
}
}
// cout<<E[22][0].first<<' '<<E[22][0].second<<'\n';
// assert(sz)
for(int i = 0;i <= sz;i++) dis[i] = 1e9;
dis[b[0]] = 0;
priority_queue<pair<int,int>>q;
q.push({0,b[0]});
while(!q.empty()){
int x = q.top().second;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
// cout<<x<<'\n';
for(auto i : E[x]){
if(dis[i.first] > dis[x] + i.second){
dis[i.first] = dis[x] + i.second;
q.push({-dis[i.first],i.first});
}
}
}
if(dis[b[1]] == 1e9) cout<<-1;
else cout<<dis[b[1]];
}
