//Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30005;
const int INF = 1000000000;
int numSkycrepers, numDoge;
vector<int> doge[MAX_N];
int dist[MAX_N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int b[MAX_N], p[MAX_N];
void dijkstra(int x)
{
for (int i = 0; i < numSkycrepers; i++)
{
dist[i] = INF;
}
dist[x] = 0;
pq.push(make_pair(0, x));
while (!pq.empty())
{
int node, w;
tie(w, node) = pq.top();
pq.pop();
if (w != dist[node])
{
continue;
}
for (auto &p : doge[node])
{
for (int u = node + p, cnt = 1; u < numSkycrepers; u += p, cnt++)
{
if (w + cnt < dist[u])
{
dist[u] = w + cnt;
pq.push(make_pair(w + cnt, u));
}
}
for (int u = node - p, cnt = 1; u >= 0; u -= p, cnt++)
{
if (w + cnt < dist[u])
{
dist[u] = w + cnt;
pq.push(make_pair(w + cnt, u));
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> numSkycrepers >> numDoge;
for (int i = 0; i < numDoge; i++)
{
cin >> b[i] >> p[i];
doge[b[i]].push_back(p[i]);
}
if (b[0] == b[1])
{
cout << 0;
return 0;
}
for (int i = 0; i < numSkycrepers; i++)
{
sort(doge[i].begin(), doge[i].end(), greater<int>());
doge[i].resize(distance(doge[i].begin(), unique(doge[i].begin(), doge[i].end())));
}
dijkstra(b[0]);
cout << (dist[b[1]] == INF ? -1 : dist[b[1]]);
return 0;
}
