#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int maxn = 3e4+5;
const int inf = 2e9;
int d[maxn][200], vis[maxn][200];
vector<pair<int, int>> vec[maxn];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
int n, m;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//ifstream cin("input.txt");
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < 200; j++)d[i][j]=2e9;
}
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
vec[a].push_back({b, i});
if(!i){
d[a][0]=0;
pq.push({0, {a, 0}});
}
}
int ans = -1;
while(!pq.empty()){
auto x = pq.top().s;
//cout << x.f << " " << x.s << endl;
pq.pop();
if(vis[x.f][x.s])continue;
if(x.s){
if(x.f - x.s >= 0 && d[x.f-x.s][x.s] > d[x.f][x.s] +1){
d[x.f-x.s][x.s] = d[x.f][x.s] +1;
pq.push({d[x.f-x.s][x.s], {x.f-x.s, x.s}});
}
if(x.f + x.s < n && d[x.f+x.s][x.s] > d[x.f][x.s] +1){
d[x.f+x.s][x.s] = d[x.f][x.s] +1;
pq.push({d[x.f+x.s][x.s], {x.f+x.s, x.s}});
}
if(d[x.f][0] > d[x.f][x.s]){
d[x.f][0]=d[x.f][x.s];
pq.push({d[x.f][0], {x.f, 0}});
}
}
else{
for(auto v: vec[x.f]){
if(v.s == 1)ans = d[x.f][0];
if(v.f < 200){
if(d[x.f][v.f] > d[x.f][0]){
d[x.f][v.f]=d[x.f][0];
pq.push({d[x.f][v.f], {x.f, v.f}});
}
}
else{
for(int j = 1; x.f-j*v.f >= 0; j++){
int pos = x.f-j*v.f;
if(d[pos][0] > d[x.f][x.s]+j){
d[pos][0] = d[x.f][x.s]+j;
pq.push({d[pos][0], {pos, 0}});
}
}
for(int j = 1; x.f+j*v.f < n; j++){
int pos = x.f+j*v.f;
if(d[pos][0] > d[x.f][x.s]+j){
d[pos][0] = d[x.f][x.s]+j;
pq.push({d[pos][0], {pos, 0}});
}
}
}
}
}
}
cout << ans;
}
