#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<ll,ll>> bird;
vector<ll> vis;
ll ans=1e18,m;
void dfs(ll u,ll cnt){
if(u==1){
ans=min(ans,cnt);
return;
}
vis[u]=1;
for(ll i=0 ; i<m ; i++){
if(vis[i]==1) continue;
if(abs(bird[i].first-bird[u].first)%bird[u].second==0){
dfs(i,cnt+abs(bird[i].first-bird[u].first)/bird[u].second);
}
}
vis[u]=0;
}
int main(){
ll n,a,b,i,j,k,q;
cin>>n>>m;
bird.resize(m);
vis.resize(m,0);
for(i=0 ; i<m ; i++){
cin>>bird[i].first>>bird[i].second;
}
dfs(0,0);
if(ans==1e18) cout<<-1<<"\n";
else cout<<ans<<"\n";
return 0;
}
