#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
char c;
bool nega=0;
while((!isdigit(c=getchar()))&&(c!='-'));
if(c=='-'){
nega=1;
c=getchar();
}
x=c-48;
while(isdigit(c=getchar())) x=x*10+c-48;
if(nega) x=-x;
}
template <typename T> inline void writep(T x){
if(x>9) writep(x/10);
putchar(x%10+48);
}
template <typename T> inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
writep(x);
}
template <typename T> inline void writeln(T x){
write(x);
putchar('\n');
}
#define taskname "Jakarta_Skyscrapers"
int n, m;
int b[30001];
int p[30001];
vector <int> big[30001];
vector <int> small[30001];
int f[30001][176];
int sq=175;
class data{
public:
int u, s, d;
data(){}
data(int _u, int _s, int _d){
u=_u;
s=_s;
d=_d;
}
};
class cmp{
public:
bool operator ()(data a, data b){
return a.d>b.d;
}
};
priority_queue <data, vector <data>, cmp> q;
const int inf=mask(30);
void dij(){
FOR(i, 0, n) FOR(j, 0, sq) f[i][j]=inf;
f[b[0]][0]=0;
q.push(data(b[0], 0, 0));
data t;
while(!q.empty()){
t=q.top();
q.pop();
if(t.d>f[t.u][t.s]) continue;
// cerr<<t.u<<" "<<t.s<<" "<<t.d<<'\n';
if(t.s){///can move
if(t.u-t.s>=0){
if(f[t.u-t.s][t.s]>t.d+1){
f[t.u-t.s][t.s]=t.d+1;
q.push(data(t.u-t.s, t.s, t.d+1));
}
}
if(t.u+t.s<n){
if(f[t.u+t.s][t.s]>t.d+1){
f[t.u+t.s][t.s]=t.d+1;
q.push(data(t.u+t.s, t.s, t.d+1));
}
}
if(t.d<f[t.u][0]){
f[t.u][0]=t.d;
q.push(data(t.u, 0, t.d));
}
}
else{
///move using small steps:
for(int i: small[t.u]){
if(f[t.u][p[i]]>f[t.u][0]){
f[t.u][p[i]]=f[t.u][0];
q.push(data(t.u, p[i], f[t.u][p[i]]));
}
}
///move using big steps:
for(int i: big[t.u]){
for(int x=b[i]%p[i]; x<=n; x+=p[i]){
if(f[x][0]>f[t.u][0]+abs(t.u-x)/p[i]){
f[x][0]=f[t.u][0]+abs(t.u-x)/p[i];
q.push(data(x, 0, f[x][0]));
}
}
}
}
}
}
int main(){
#ifdef Kanikou
if(fopen(taskname".inp", "r"))
freopen(taskname".inp", "r", stdin);
#endif // Kanikou
read(n);
read(m);
FFOR(i, 0, m){
read(b[i]);
read(p[i]);
if(p[i]<sq) small[b[i]].pb(i);
else big[b[i]].pb(i);
}
dij();
int ans=f[b[1]][0];
// for(int x=b[1]%p[1]; x<n; x+=p[1]) ans=min(ans, f[x][0]+abs(b[1]-x)/p[1]);
if(ans==inf) ans=-1;
writeln(ans);
}
