#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
int i, va, j, k, t, n, m, mi[30001]; pair<int, int> p[30001]; vector<int> v[30001]; bool c[30001];
void run(){
cin >> n >> m;
for( i = 1; i <= m; i++) cin >> p[i].first >> p[i].second, v[p[i].first].push_back(p[i].second);
for( i = 0; i < n; i++) mi[i] = 1e9, c[i] = 0;
mi[0] = 0;
priority_queue<pair<int, int>> p; p.push({-mi[0], 0});
while(!p.empty()){
t = p.top().second; p.pop();
if(c[t]) continue;
c[t] = 1;
for(int x: v[t]){
for( i = t % x; i < n; i+=x) if(mi[i] > mi[t]+abs(t-i)/x) mi[i] = mi[t]+abs(t-i)/x, p.push({-mi[i], i});
}
}
if(mi[1] == 1e9) cout << -1;
else cout << mi[1];
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// int tt; cin >> tt; while(tt--)
run();
}
