#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
ll mod = 1e9+7 ;
const int N = 3e4+23;
const ll INF= 1e18+23;
vector<int> g[N];
int d[N];
int b[N];
int n , m;
ll dist[N];
int vis[N];
void bfs(){
fast_io
for (int i=0; i<=n; i++) dist[i]=INF;
dist[b[0]]=0;
priority_queue<pll, vector<pll>, greater<pll> > q;
q.push({0, b[0]});
while(!q.empty()){
int v=q.top().S; q.pop();
if(vis[v]) continue;
vis[v]=1;
for (int d: g[v]){
for (int i=1; v+i*d<n; i++){
int u=i*d+v;
if(dist[u]>dist[v]+i){
dist[u]=dist[v]+i;
q.push({dist[u], u});
}
}
for (int i=1; v-i*d>=0; i++){
int u=-i*d+v;
if(dist[u]>dist[v]+i){
dist[u]=dist[v]+i;
q.push({dist[u], u});
}
}
}
}
}
int main()
{
cin>>n>>m;
for (int i=0; i<m; i++) cin>>b[i]>>d[i];
for (int i=0; i<m; i++) g[b[i]].pb(d[i]);
bfs();
if(dist[b[1]]>=INF) dist[b[1]]=-1;
cout<<dist[b[1]]<<endl;
}
