#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 30010;
const ll inf = 1e9;
struct doge
{
int b, p;
} d[maxn];
struct edge
{
int u;
ll w;
edge(int _u, ll _w)
{
u = _u;
w = _w;
}
bool operator < (const edge &e) const
{
return w > e.w;
}
};
bitset < 2010 > g[2010];
int n, m, used[2010][2010], op[2010];
int dp[2010];
void dijkstra(int s)
{
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= n; j ++)
used[i][j] = -1;
for (int i = 0; i <= n; i ++)
op[i] = -1;
queue < int > q;
q.push(d[0].b);
op[d[0].b] = 0;
while(!q.empty())
{
int cur = q.front();
q.pop();
int pos = g[cur]._Find_next(0);
while(pos < n)
{
if (used[cur][pos] == -1)
used[cur][pos] = op[cur];
///cout << cur << " : " << pos << " : " << used[cur][pos] << endl;
int nb = cur + pos;
if (nb < n && used[nb][pos] == -1)
{
used[nb][pos] = used[cur][pos] + 1;
if (op[nb] == -1)
op[nb] = used[cur][pos] + 1;
g[nb][pos] = 1;
q.push(nb);
}
nb = cur - pos;
if (nb >= 0 && used[nb][pos] == -1)
{
used[nb][pos] = used[cur][pos] + 1;
if (op[nb] == -1)
op[nb] = used[cur][pos] + 1;
g[nb][pos] = 1;
q.push(nb);
}
g[cur][pos] = 0;
pos = g[cur]._Find_next(pos);
}
}
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < m; i ++)
{
cin >> d[i].b >> d[i].p;
}
for (int i = 0; i < m; i ++)
{
g[d[i].b][d[i].p] = 1;
}
dijkstra(0);
cout << op[d[1].b] << endl;
}
int main()
{
solve();
return 0;
}
/**
7 2
2 7
2 10
*/
