#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int MAX_M = 30000;
int dist0[MAX_M];
struct doge
{
int p;
};
bool operator < (doge X, doge Y)
{
if(dist0[X.p] == dist0[Y.p]) return X.p < Y.p;
return dist0[X.p] < dist0[Y.p];
}
int main()
{
int N, M;
cin >> N >> M;
int B[M], P[M];
vector<int> doge_pos[N];
for(int i = 0; i < M; i++)
{
cin >> B[i] >> P[i];
doge_pos[ B[i] ].push_back(i);
}
dist0[0] = 0;
for(int i = 1; i < M; i++) dist0[i] = 2000000000;
set<doge> dogeset;
for(int i = 0; i < M; i++) dogeset.insert(doge{i});
while(!dogeset.empty())
{
doge g = *dogeset.begin();
dogeset.erase(g);
int i = g.p;
for(int v = B[i] % P[i]; v < N; v += P[i]) for(int j: doge_pos[v]) if(i != j) {
int weight = abs((B[j] - B[i]) / P[i]);
if (dist0[j] > dist0[i] + weight) {
dogeset.erase(doge{j});
dist0[j] = dist0[i] + weight;
dogeset.insert(doge{j});
}
}
}
if(dist0[1] == 2000000000) cout << "-1\n";
else cout << dist0[1] << '\n';
return 0;
}
