#include <bits/stdc++.h>
using namespace std;
const int nx=3e4+5, tx=180;
int n, m, st, ed, s[nx], p[nx], dp[tx][nx], dp2[nx][2*tx];
vector<int> v[nx];
deque<tuple<int, int, int, int>> q;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m>>s[0]>>p[0]>>s[1]>>p[1]; v[s[1]].push_back(1);
for (int i=1; i<m-1; i++) cin>>s[i+1]>>p[i+1], v[s[i+1]].push_back(i+1);
for (int i=0; i<tx; i++) for (int j=0; j<nx; j++) dp[i][j]=INT_MAX;
for (int i=0; i<nx; i++) for (int j=0; j<2*tx; j++) dp2[i][j]=INT_MAX;
int t=sqrt(n);
if (p[0]>=t) dp2[0][tx]=0;
else dp[p[0]][s[0]]=0;
q.push_back({0, p[0], s[0], 0});
while (!q.empty())
{
auto [w, c, l, idx]=q.front();
//printf("%d %d %d %d\n", w, c, l, idx);
q.pop_front();
if (c>=t)
{
if (l+c<n&&w+1<dp2[idx][(l+c-s[idx])/p[idx]+tx]) dp2[idx][(l+c-s[idx])/p[idx]+tx]=w+1, q.push_back({w+1, c, l+c, idx});
if (l-c>=0&&w+1<dp2[idx][(l-c-s[idx])/p[idx]+tx]) dp2[idx][(l-c-s[idx])/p[idx]+tx]=w+1, q.push_back({w+1, c, l-c, idx});
}
else
{
if (l+c<n&&w+1<dp[c][l+c]) dp[c][l+c]=w+1, q.push_back({w+1, c, l+c, idx});
if (l-c>=0&&w+1<dp[c][l-c]) dp[c][l-c]=w+1, q.push_back({w+1, c, l-c, idx});
}
for (auto nw:v[l])
{
if (nw==1)
{
cout<<w;
return 0;
}
if (p[nw]>=t&&w<dp2[nw][tx]) dp2[nw][tx]=w, q.push_front({w, p[nw], l, nw});
if (p[nw]<t&&w<dp[p[nw]][l]) dp[p[nw]][l]=w, q.push_front({w, p[nw], l, nw});
}
}
cout<<-1;
}
