#include <bits/stdc++.h>
using namespace std;
vector<int> nbJumps;
vector<vector<int>> jump_count;
int main () {
int nbSky, nbDoge;
cin >> nbSky >> nbDoge;
nbJumps.resize(nbSky, -1);
jump_count.resize(nbSky);
int sx = 0;
int ex = 0;
for (int idDoge = 0; idDoge < nbDoge; idDoge ++) {
int x, p;
cin >> x >> p;
if (idDoge == 0) sx = x;
if (idDoge == 1) ex = x;
jump_count[x].push_back(p);
}
set<pair<int, int>> mp;
nbJumps [sx] = 0;
mp.insert({ sx, 0 });
while (mp.size() != 0) {
pair<int, int> mu = * mp.begin();
mp.erase(mu);
int curx = mu.second;
if (curx == ex) break ;
for (int jump : jump_count[curx]) {
int i = 1;
for (int nx = curx - jump; nx >= 0; nx -= jump) {
if (nbJumps[nx] == -1 || nbJumps[nx] > nbJumps[curx] + i) {
if (nbJumps[nx] != -1)
mp.erase({ nbJumps[nx], nx });
nbJumps[nx] = nbJumps[curx] + i;
mp.insert({ nbJumps[nx], nx });
}
i ++;
}
i = 1;
for (int nx = curx + jump; nx < nbSky; nx += jump) {
if (nbJumps[nx] == -1 || nbJumps[nx] > nbJumps[curx] + i) {
if (nbJumps[nx] != -1)
mp.erase({ nbJumps[nx], nx });
nbJumps[nx] = nbJumps[curx] + i;
mp.insert({ nbJumps[nx], nx });
}
i ++;
}
}
}
cout << nbJumps[ex];
}
