#include <bits/stdc++.h>
using namespace std;
const int oo = INT_MAX;
const int nmax = 3e4;
const int bsize = 173;
int n,m;
int b[nmax + 5], p[nmax + 5];
int r[nmax + 5][bsize + 5];
int d[nmax + 5], d_l[nmax + 5][bsize + 5];
bool sel[nmax + 5], sel_l[nmax + 5][bsize + 5];
vector<int> l[nmax + 5];
typedef pair<int,pair<int,int>> pi;
priority_queue <pi,vector<pi>,greater<pi>> h;
void switch_doge(int t, int poz)
{
sel[poz] = true;
d[poz] = t;
for(auto ln : l[poz])
{
if(ln < bsize)
{
if(poz - ln >= 0 && t + 1 < d_l[poz - ln][ln])
{
d_l[poz - ln][ln] = t + 1;
h.push({t + 1, {poz - ln, ln}});
}
if(poz + ln < n && t + 1 < d_l[poz + ln][ln])
{
d_l[poz + ln][ln] = t + 1;
h.push({t + 1, {poz + ln, ln}});
}
}
else
{
for(int i=poz;i>=0;i-=ln)
{
int t_aux = t + (poz - i) / ln;
if(t_aux < d[i])
{
d[i] = t_aux;
h.push({t_aux,{i,ln}});
}
}
for(int i=poz+ln;i<n;i+=ln)
{
int t_aux = t + (i - poz) / ln;
if(t_aux < d[i])
{
d[i] = t_aux;
h.push({t_aux,{i,ln}});
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n>>m;
for(int i=0; i<n; i++)
{
d[i] = oo;
for(int ln=1; ln<bsize; ln++)
{
r[i][ln] = oo;
d_l[i][ln] = oo;
}
}
for(int i=0; i<m; i++)
{
cin>>b[i]>>p[i];
l[b[i]].push_back(p[i]);
}
h.push({0,{b[0],p[0]}});
if(b[0] < bsize)
{
d_l[b[0]][p[0]] = 0;
}
while(!h.empty())
{
while(!h.empty())
{
int poz = h.top().second.first;
int ln = h.top().second.second;
if(ln < bsize)
{
if(sel_l[poz][ln])
{
h.pop();
continue;
}
else
{
break;
}
}
else
{
if(sel[poz])
{
h.pop();
continue;
}
else
{
break;
}
}
}
if(h.empty())
{
break;
}
int t = h.top().first;
int poz = h.top().second.first;
int ln = h.top().second.second;
h.pop();
if(!sel[poz])
{
switch_doge(t,poz);
}
if(ln < bsize)
{
sel_l[poz][ln] = true;
if(poz - ln >= 0 && t + 1 < d_l[poz - ln][ln])
{
d_l[poz - ln][ln] = 1 + t;
h.push({1 + t, {poz - ln, ln}});
}
if(poz + ln < n && t + 1 < d_l[poz + ln][ln])
{
d_l[poz + ln][ln] = 1 + t;
h.push({1 + t, {poz + ln, ln}});
}
}
}
int rez = d[b[1]];
if(rez==oo)
{
cout<<-1<<'\n';
return 0;
}
cout<<rez<<'\n';
return 0;
}
