#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double doublel;
#define f first
#define s second
const int N = 3e5 + 100;
const ll base = 313;
const ll mod = 1e9 + 9;
const int inf = 1e8;
int dis[N], b[N];
vector<int> adj[N];
priority_queue<pair<int, int>> q;
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int p;
cin >> b[i] >> p;
adj[b[i]].push_back(p);
}
for(int i = 0; i < n; i++)
dis[i] = inf;
dis[b[0]] = 0;
q.push({0, b[0]});
while(!q.empty())
{
int x = q.top().s;
q.pop();
for(auto p : adj[x])
{
int c = 1;
for(int i = x+p; i < n; i += p)
{
if(dis[i] > dis[x] + c)
{
dis[i] = dis[x] + c;
q.push({-dis[i], i});
}
c++;
}
c = 1;
for(int i = x-p; i >= 0; i -= p)
{
if(dis[i] > dis[x] + c)
{
dis[i] = dis[x] + c;
q.push({-dis[i], i});
}
c++;
}
}
}
if(dis[1] >= inf)
dis[1] = -1;
cout << dis[1] << endl;
return 0;
}
