#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int dp[30001];
vector<int> G[30001];
int A[30001][2];
int main(){
int n, k;
cin >> n >> k;
for(int i = 0; i < k; i++){
cin >> A[i][0] >> A[i][1];
G[A[i][0]].push_back(A[i][1]);
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, A[0][0]});
fill(dp, dp + n, (1 << 30));
while(q.size()){
pair<int, int> qe = q.top(); q.pop();
int v = qe.se, w = qe.fi;
if(dp[v] != (1 << 30)) continue;
dp[v] = w;
// cout << v << ' ' << w << endl;
for(auto i : G[v]){
for(int j = v % i; j < n; j += i){
int d = abs(v - j) / i;
if(dp[j] > w + d) q.push({w + d, j});
}
}
}
cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}
