#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
vector<int> b,p;
vector<set<int> > v;
int target;
map<pair<int,int>,bool> vis;
vector<bool> vi;
int bfs()
{
queue<pair<pair<int,int>,int> > q;
q.push({{0,0},0});
vis[{0,0}] = true;
while(!q.empty())
{
int d = q.front().second;
int pos= q.front().first.first;
int power = q.front().first.second;
q.pop();
if(pos==target) return d;
if(!vis[{pos+power,power}] && power+pos<m)
{
q.push({{pos+power,power},d+1});
vis[{pos+power,power}] = true;
}
if(!vis[{pos-power,power}] && pos-power>=0)
{
q.push({{pos-power,power},d+1});
vis[{pos-power,power}] = true;
}
if(!vi[pos])
{
for(auto it:v[pos])
{
if(!vis[{pos+it,it}] && it+pos<m) q.push({{pos+it,it},d+1});
if(!vis[{pos-it,it}] && pos-it>=0) q.push({{pos-it,it},d+1});
}
vi[pos] = true;
}
}
return -1;
}
main()
{
cin>>m>>n;
b.resize(n);
p.resize(n);
v.resize(m);
vi.assign(m,false);
for(int i=0;i<n;i++)
{
cin>>b[i]>>p[i];
v[b[i]].insert(p[i]);
if(i==1) target = b[i];
}
/*g.resize(n);
for(int i=0;i<n;i++)
{
for(int j=i-p[i];j>=0;j-=p[i])
{
g[i].push_back(v[j]);
}
for(int j=i+p[i];j<m;j+=p[i])
{
g.push_back(v[j]);
}
}*/
cout<<bfs()<<endl;
}
