#include "brperm.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 5e5 + 5 , LG = 20 , P = 131;
int n , t; ull p[LG] = {P} , f[LG][N] , h[LG][N] , iv[LG][N];
ull Qpow(ull x , ull p = (1llu << 63) - 1)
{
  ull res = 1;
  for(; p ; p >>= 1 , x = x * x)
    if(p & 1)res = x * res;
  return res;
}
ull Get(int k , int l , int r){return (h[k][r] - h[k][l - 1]) * iv[t - k][l - 1];}
void init(int n, const char s[]) {

  ::n = n , t = __lg(n);
  for(int i = 1 ; i <= t ; i++)
    p[i] = p[i - 1] * p[i - 1];
  for(int i = 0 ; i <= t ; i++)
  {
    iv[i][0] = 1; 
    iv[i][1] = Qpow(p[i]);
    for(int j = 2 ; j <= n ; j++)
      iv[i][j] = iv[i][j - 1] * iv[i][1];
  }
  for(int i = 1 ; i <= n ; i++)f[0][i] = s[i - 1];
  for(int i = 1 ; i <= t ; i++)
    for(int j = 1 ; j + (1 << i) - 1 <= n ; j++)
      f[i][j] = f[i - 1][j] + p[t - i] * f[i - 1][j + (1 << (i - 1))];

  for(int i = 0 ; i <= t ; i++)
  {
    ull pw = 1;
    for(int j = 1 ; j <= n ; j++)
    {
      h[i][j] = h[i][j - 1] + s[j - 1] * pw;
      pw = pw * p[t - i];
    }
  }
  return;
}
int query(int l, int k) 
{
  int r = (++l) + (1 << k) - 1;
  if(r > n)return 0;
  return f[k][l] == Get(k , l , r);
}

/*













































#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];

void solve() {
    int n, m; cin >> n >> m;
    int curv = n;
    map<pair<int, int>, int> pos;
    int p0, p1;
    for (int i = 0; i < m; i++) {
        int b, g; cin >> b >> g;
        if (i == 0) p0 = b;
        if (i == 1) p1 = b;
        if (pos.find({b % g, g}) != pos.end()) {
            int step = (b - b % g) / g;
            g_lol[b].pb(pos[{b % g, g}] + step);
            continue;
        }
        pos[{b % g, g}] = curv;
        int step = (b - b % g) / g;
        g_lol[b].pb(pos[{b % g, g}] + step);
        for (int j = b % g; j < n; j += g) {
            val[curv] = j;
            stepp[curv] = g;
            curv++;
        }
    }
    for (int i = 0; i < curv; i++) dist[i] = 1e9;
    dist[p0] = 0;

    deque<int> q;
    q.push_back(p0);
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        if (v < n) {
            for (int el : g_lol[v]) {
                if (dist[el] > dist[v]) {
                    dist[el] = dist[v];
                    q.push_front(el);
                }
            }
        } else {
            if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
                dist[v - 1] = dist[v] + 1;
                q.push_back(v - 1);
            }
            if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
                dist[v + 1] = dist[v] + 1;
                q.push_back(v + 1);
            }
            if (dist[val[v]] > dist[v]) {
                dist[val[v]] = dist[v];
                q.push_front(val[v]);
            }
        }
    }
    cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];

void solve() {
    int n, m; cin >> n >> m;
    int curv = n;
    map<pair<int, int>, int> pos;
    int p0, p1;
    for (int i = 0; i < m; i++) {
        int b, g; cin >> b >> g;
        if (i == 0) p0 = b;
        if (i == 1) p1 = b;
        if (pos.find({b % g, g}) != pos.end()) {
            int step = (b - b % g) / g;
            g_lol[b].pb(pos[{b % g, g}] + step);
            continue;
        }
        pos[{b % g, g}] = curv;
        int step = (b - b % g) / g;
        g_lol[b].pb(pos[{b % g, g}] + step);
        for (int j = b % g; j < n; j += g) {
            val[curv] = j;
            stepp[curv] = g;
            curv++;
        }
    }
    for (int i = 0; i < curv; i++) dist[i] = 1e9;
    dist[p0] = 0;

    deque<int> q;
    q.push_back(p0);
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        if (v < n) {
            for (int el : g_lol[v]) {
                if (dist[el] > dist[v]) {
                    dist[el] = dist[v];
                    q.push_front(el);
                }
            }
        } else {
            if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
                dist[v - 1] = dist[v] + 1;
                q.push_back(v - 1);
            }
            if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
                dist[v + 1] = dist[v] + 1;
                q.push_back(v + 1);
            }
            if (dist[val[v]] > dist[v]) {
                dist[val[v]] = dist[v];
                q.push_front(val[v]);
            }
        }
    }
    cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}





































114514?
*/