#include<bits/stdc++.h>
using namespace std;
const int k = 200;
int haha[30001][301];
int bruh[30001][301];
vector<int> idk[30001];
vector<pair<int,int>> mon(0);
queue<pair<int,int>> banana;
void ins(int s, int x) {
for(int v: idk[s]) {
int p = mon[v].first,d = mon[v].second;
if(d < k) {
haha[p][d] = x;
}
else {
bruh[v][p/d] = x;
}
banana.push({v,p});
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,a,b;
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++) {
haha[i][j] = -1;
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < 201; j++) {
bruh[i][j] = -1;
}
}
for(int i = 0; i < m; i++) {
cin >> a >> b;
mon.push_back({a,b});
idk[a].push_back(i);
}
int s = mon[0].first;
ins(s,0);
vector<bool> apple(n);
apple[s] = true;
while(!banana.empty()) {
int v = banana.front().first,p = banana.front().second;
banana.pop();
int d = mon[v].second;
int x;
if(d < k) {
x = haha[p][d];
if(p >= d && haha[p-d][d] == -1) {
haha[p-d][d] = x+1;
banana.push({v,p-d});
}
if(p < n-d && haha[p+d][d] == -1) {
haha[p+d][d] = x+1;
banana.push({v,p+d});
}
}
else {
int c = p/d;
x = bruh[v][c];
if(p >= d && bruh[v][c-1] == -1) {
bruh[v][c-1] = x+1;
banana.push({v,p-d});
}
if(p < n-d && bruh[v][c+1] == -1) {
bruh[v][c+1] = x+1;
banana.push({v,p+d});
}
}
if(p >= d && apple[p-d] == false) {
apple[p-d] = true;
ins(p-d,x+1);
}
if(p < n-d && apple[p+d] == false) {
apple[p+d] = true;
ins(p+d,x+1);
}
}
int t = mon[1].first;
int ans = INT_MAX;
for(int i = 1; i < k; i++) {
if(haha[t][i] != -1) {
ans = min(ans,haha[t][i]);
}
}
for(int i = 0; i < m; i++) {
if(mon[i].second >= k && bruh[i][t/mon[i].second] != -1 && t%mon[i].second == mon[i].first%mon[i].second) {
ans = min(ans,bruh[i][t/mon[i].second]);
}
}
if(ans == INT_MAX) {
cout << -1;
}
else {
cout << ans;
}
return 0;
}
