#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 3e4 + 10;
const int M = 3e4 + 10;
const ll inf = 1e18;
#define F first
#define S second
#define pb push_back
#define kill(x) cout<<x<<endl, exit(0);
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lc (v << 1)
#define rc ((v<<1) |1)
//#define int short
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
int n,m;
vector<int> here[N];
bool vis[N];
vector<bool> mark[M],mk[M];
deque<pair<pii,int>> dq;
//int dist[M][N];
int b[M],p[M];
void bfs() {
mark[0][b[0]] = 1;
dq.push_front({{0,b[0]},0});
mk[p[0]][b[0]%p[0]] = 1;
while(sz(dq)) {
auto [sex,d] = dq.front(); dq.pop_front();
auto [id,pos] = sex;
//debug((int)id,(int)pos);
if(id == 1) {
kill(d);
}
mk[p[id]][b[id] %p[id]] = 1;
if(!vis[pos]) {
for(int x : here[pos]) {
if(!mark[x][pos]) {
mark[x][pos] = 1;
if(x == 1) kill(d);
if(!mk[p[x]][b[x]%p[x]])
dq.push_front({{x,pos},d});
}
}
vis[pos] = true;
}
// front
if(pos+ p[id] < n && !mark[id][pos + p[id]]) {
mark[id][pos + p[id]] = true;
//dist[id][pos + p[id]] = dist[id][pos] + 1;
dq.push_back({{id,pos+p[id]},d+1});
}
// back
if(pos- p[id] >=0 && !mark[id][pos - p[id]]) {
mark[id][pos - p[id]] = true;
//dist[id][pos - p[id]] = dist[id][pos] + 1;
dq.push_back({{id,pos-p[id]},d+1});
}
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
for(int i = 0 ;i < M; i ++) {
mark[i].resize(M);
mk[i].resize(M);
}
cin>>n>>m;
for(int i = 0 ; i <m; i++) {
cin>>b[i]>>p[i];
here[b[i]].pb(i);
}
bfs();
kill(-1);
return 0;
}
