#include<bits/stdc++.h>
#define tizoboz ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
#define int long long
#define itn int
#define ss set <int>
#define prq priority_queue <int>
#define endl '\n'
const ll MOD = 1e9 + 7;
#define md(x) (((x%MOD)+MOD)%MOD)
#define vi vector <int>
#define vl vector<ll>
#define str string
#define mp make_pair
#define mata int32_t
#define sz size
#define lc id *2
#define rc lc +1
#define SZ(x) (int)x.size()
#define mid (l+r)/2
#define cn cin
#define ct cout
#define sep " "
#define F first
#define X first
#define S second
#define Y second
using namespace std;
typedef pair <int , int> pii;
const int maxn = 3e4 + 5;
vi g[maxn];
bool use[maxn];
int dist[maxn];
int n , m;
const int inf = 1e9;
void solve(){
cn >> n >> m;
vi b(m) , p(m);
for (int i = 0 ; i < maxn ; i ++) dist[i] = inf;
for (int i = 0 ; i < m ; i ++){
cn >> b[i] >> p[i];
g[b[i]].pb(p[i]);
}
int nd = b[0];
dist[nd] = 0;
while (!use[b[1]] and nd != -1){
use[nd] = 1;
for (auto it : g[nd]){
for (int j = 1 ; nd + j*it < n ; j++){
dist[nd+j*it] = min (dist[nd + j*it] , dist[nd] + j);
}
for (int j = 1 ; nd-j*it >= 0 ; j++){
dist[nd -j*it] = min (dist[nd -j*it] , dist[nd] + j);
}
}
nd = -1;
for (int i = 0 ; i < n ; i++){
if (use[i]) continue;
if (dist[i] == 1e9) continue;
if (nd == -1 || dist[nd] > dist[i]) nd =i;
}
}
if(dist[b[1]]==1e9) dist[b[1]]=-1;
cout<<dist[b[1]];
}
mata main(){
tizoboz;
int tt = 1;
// cn >> tt;
while (tt--){
solve();
}
return 0;
}
