#include<bits/stdc++.h>
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
typedef long long llong;
const int MAXN = 3e4 + 10;
const int INF = 1e9 + 10;
struct Edge
{
int to, cost;
Edge(){};
Edge(int to, int cost)
{
this->to = to;
this->cost = cost;
}
friend bool operator<(const Edge &e1, const Edge &e2)
{
return e1.cost > e2.cost;
}
};
int n, m;
int start, finish;
int p[MAXN];
int power[MAXN];
int dist[MAXN];
vector < int > poss[MAXN];
void read()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
cin >> p[i] >> power[i];
p[i]++;
}
start = p[1];
finish = p[2];
for(int i = 1; i <= m; i++)
{
poss[p[i]].push_back(power[i]);
}
}
void solve()
{
for(int i = 1; i <= n; i++)
{
dist[i] = INF;
}
priority_queue < Edge > pq;
dist[start] = 0;
pq.push(Edge(start, 0));
while(!pq.empty())
{
Edge t = pq.top();
pq.pop();
int u = t.to;
if(t.cost > dist[u])
continue;
for(int len : poss[u])
{
for(int jumps = 1; u + len * jumps <= n; jumps++)
{
int v = u + len * jumps;
if(dist[u] + jumps < dist[v])
{
dist[v] = dist[u] + jumps;
pq.push(Edge(v, dist[v]));
}
}
for(int jumps = 1; u - len * jumps >= 1; jumps++)
{
int v = u - len * jumps;
if(dist[u] + jumps < dist[v])
{
dist[v] = dist[u] + jumps;
pq.push(Edge(v, dist[v]));
}
}
}
}
if(dist[finish] == INF)
{
cout << -1 << endl;
}
else
{
cout << dist[finish] << endl;
}
}
int main()
{
speed();
read();
solve();
return 0;
}
