#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 3e3+20,mod = 1e9+7,inf = 1e9,sq = 400;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int n,ll k){
int c = 1;
while (k){
if (k&1) c = (1ll*c*n)%mod;
n = (1ll*n*n)%mod;
k >>= 1;
}
return c;
}
int e[N][N],d[N];
int n,a[N],p[N];
inline void dij(){
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0,a[0]});
d[a[0]] = 0;
while (!pq.empty()){
pll p = pq.top();
int y = p.Y;
pq.pop();
rep(i,0,n){
if (d[i] > d[y] && d[i]-d[y] > e[y][i]){
d[i] = d[y]+e[y][i];
pq.push({d[i],i});
}
}
}
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(e,127,sizeof e);
memset(d,127,sizeof d);
ll Inf = d[0];
int m;
cin >> n >> m;
rep(i,0,m){
cin >> a[i] >> p[i];
if (i == 1) continue;
int x = a[i];
int t = 0;
while (x < n){
e[a[i]][x] = min(e[a[i]][x],t);
x += p[i];
t++;
}
x = a[i]-p[i];
t = 1;
while (x >= 0){
e[a[i]][x] = min(e[a[i]][x],t);
t++;
x -= p[i];
}
}
dij();
if (d[a[1]] >= Inf) cout << -1;
else
cout << d[a[1]];
}
