#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// using namespace __gnu_pbds;
typedef long long ll;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define vpi vector<pair<int,int>>
#define rep(ii,st, n) for(int ii=st; ii<n; ii++)
#define gp " "
//bit_manupulation
#define checkbit(x,n) (x&(1LL<<n))
#define setbit(x,n) (x=(x|(1LL<<n)))
#define resetbit(x,n) (x=(x&(~(1LL<<n))))
#define pow2(i) (1LL<<i)
#define bitcnt(x) ((sizeof(x) <= sizeof(int)) ? (32 - __builtin_clz(x)) : (64 - __builtin_clzll(x)))
// #define DEBG
#define debug(n)
#define debugc(a)
#define debugcc(a)
#ifdef DEBG
#define debug(n) cout<<__LINE__<<gp<<#n<<gp<<n<<endl;
#define debugc(a) cout<<__LINE__<<gp<<#a<<gp<<'['<<gp;for(auto el:a){cout<<el<<gp;}cout<<']'<<endl;
#define debugcc(a) cout<<__LINE__<<gp<<#a<<gp<<'['<<gp;for(auto el:a){cout<<'{'<<gp<<el.ff<<','<<el.ss<<gp<<'}'<<gp;}cout<<']'<<endl;
#endif
#define fastcin() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'
#define All(a) a.begin(),a.end()
template<typename T> void get_vector(T&a){for(auto&e:a)cin>>e;}
template<typename T> void put_vector(T a){for(auto e:a)cout<<e<<" ";cout<<endl;}
const ll INF = 2e18;
const ll inf = INT_MAX;
const ll M = 2007;
const ll N = 107;
const ll modinvof2 = 500000004;
//==============================CODE STARTS HERE==============================//
int n,m;
vi b(M),p(M);
map<int,vi>mp;
// vector<vector<int>>visited(N, vi(M));
vector<vector<vector<int>>>dpp;
int func(int si, int i, int who){
if(i<0 || i>=n) return 1e16;
if(i == b[1]){
return 0;
}
if(dpp[si][i][who] != -1) return dpp[si][i][who];
int ans = 1e16;
if(si != 2) ans = min(ans,func(1, i+p[who], who)+1);
if(si != 1) ans = min(ans,func(2, i-p[who], who)+1);
for(auto& el: mp[i]){
ans = min(ans,func(1, i+p[el], el)+1);
ans = min(ans,func(2, i-p[el], el)+1);
}
return dpp[si][i][who] = ans;
}
void preprocessing(){
}
void solve(int testcases){
cin>>n>>m;
dpp.resize(3, vvi(n+7, vi(m+7)));
rep(i,0,3){
rep(j,0,n+3){
rep(k,0,m+3){
dpp[i][j][k] = -1;
}
}
}
for(int i = 0; i<m; i++){
cin>>b[i]>>p[i];
mp[b[i]].push_back(i);
}
for(auto& el: mp){
debug(el.first)
debugc(el.second)
}
int mx = 0;
bool fl = false;
int ans = func(0,0, 0);
if(ans >= 1e13){
cout<<-1<<endl;
return;
}
cout<<ans<<endl;
}
int32_t main(){
fastcin();
int t=1;
// cin>>t;
preprocessing();
rep(i,1,t+1){
solve(i);
}
return 0;
}
