#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
/* Author: Pham Gia Phuoc */
const ll MOD = (ll)(1e9) + 1LL * 19972207;
template <class T1, class T2>
void add(T1 &a, T2 b){
a += b;
if(a >= MOD) a -= MOD;
}
template <class T1, class T2>
void sub(T1 &a, T2 b){
a -= b;
if(a < 0) a += MOD;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if(a > b){a = b; return true;} return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if(a < b){a = b; return true;} return false;
}
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
const int MAX = 30010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;
int N, M;
vector <int> adj[MAX];
int S, T;
void init(){
cin >> N >> M;
for(int i = 0; i < M; i++){
int a, b; cin >> a >> b;
adj[a].push_back(b);
if(i == 0) S = a;
if(i == 1) T = a;
}
}
int dist[MAX];
bool vis[MAX];
int dijkstra(int s, int t){
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
dist[s] = 0;
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
#define PUSH(u) pq.push(make_pair(dist[u], u))
PUSH(s);
while(!pq.empty()){
int du = pq.top().fi;
int u = pq.top().se;
pq.pop();
if(!vis[u]){
vis[u] = 1;
for(int p:adj[u]){
for(int i = 1; u + i * p < N; i++){
int v = u + i * p;
if(minimize(dist[v], dist[u] + i)) PUSH(v);
}
for(int i = -1; u + i * p >= 0; i--){
int v = u + i * p;
if(minimize(dist[v], dist[u] + abs(i))) PUSH(v);
}
}
}
}
return dist[t];
}
void solve(){
int ans = dijkstra(S, T);
// int ans = 0;
if(ans >= oo) cout << -1;
else cout << ans;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define test "test"
srand(time(0));
int t = 1;
while(t--){
// gen();
init();
solve();
}
return 0;
}
/*** ROAD TO VOI 2025 ***/
