#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 30010;
const int MX = (int)4e6;
const int inf = (int)1e9;
int dist[N];
vector<int> id[MX];
vector<int> q[N];
int main(){
fastIO;
int n, m;
cin >> n >> m;
int st = -1, en = -1;
int xi, yi;
for(int i = 0 ; i < n; i ++ ){
dist[i] = inf;
}
for(int i = 0 ; i < m; i ++ ){
cin >> xi >> yi;
q[xi].push_back(yi);
if(i == 0){
st = xi;
}
else if(i == 1){
en = xi;
}
}
id[0].push_back(st);
dist[st] = 0;
for(int i = 0 ; i < MX; i ++ ){
if(id[i].empty()) continue;
for(auto x : id[i]){
if(dist[x] != i) continue;
for(auto y : q[x]){
for(int f = 1; x + y * f < n; f ++ ){
if(dist[x + y * f] > i + f){
dist[x + y * f] = i + f;
id[i + f].push_back(x + y * f);
}
}
for(int f = 1; x - y * f >= 0; f ++ ){
if(dist[x - y * f] > i + f){
dist[x - y * f] = i + f;
id[i + f].push_back(x - y * f);
}
}
}
}
}
if(dist[en] == inf)
cout << -1;
else
cout << dist[en];
return 0;
}
