#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define Mp make_pair
#define sep ' '
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define kill(res) cout << res << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 3e4 + 50;
const ll inf = 15e8;
int n, m, b[N], dist[N];
bool mark[N];
vector<int> pw[N];
void dijk(int v){
fill(dist, dist + N, inf);
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push(Mp(0, v)); dist[v] = 0;
while(!pq.empty()){
int v = pq.top().S; pq.pop();
if(mark[v]) continue;
mark[v] = true;
for(int p: pw[v]){
for(int u = v+p, i = 1; u < n; u += p, i++){
if(dist[u] > dist[v] + i){
dist[u] = dist[v] + i;
pq.push(Mp(dist[u], u));
}
}
for(int u = v-p, i = 1; u >= 0; u -= p, i++){
if(dist[u] > dist[v] + i){
dist[u] = dist[v] + i;
pq.push(Mp(dist[u], u));
}
}
}
}
}
int main(){
fast_io;
cin >> n >> m;
int p;
for(int i = 0; i < m; i++){
cin >> b[i] >> p;
pw[b[i]].pb(p);
}
dijk(b[0]);
if(dist[b[1]] >= inf) kill(-1);
kill(dist[b[1]]);
}
