#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 = 1e18;
const ll M = 1e5+7;
const ll N = 1e5+7;
const ll modinvof2 = 500000004;
//==============================CODE STARTS HERE==============================//
int n,m;
vi b,p;
map<int,set<int>>mp;
vector<bool>mark;
// const long long inf = 1e18;
struct Node{
long long at;
long long cost;
};
bool operator<(Node A, Node B){
return A.cost>B.cost; // The node with higher cost is defined as smaller
}
struct edge{
long long at;
long long cost;
edge(pair<int,int> p){
at = p.ff;
cost = p.ss;
}
};
vector<long long> distance(vector<vector<edge>>G,int source){
priority_queue<Node>Q;
vector<long long>distance(G.size(),inf);
Q.push({source,0});
distance[source] = 0;
while(!Q.empty()){
Node u = Q.top();
Q.pop();
if(mark[u.at])continue;
mark[u.at] = 1;
for(auto v:G[u.at]){
if(distance[v.at]>distance[u.at]+v.cost){
distance[v.at] = distance[u.at]+v.cost;
Q.push({v.at,distance[v.at]});
}
}
}
return distance;
}
vector<vector<edge>>g;
void preprocessing(){
}
void solve(int testcases){
cin>>n>>m;
// exit(0);
b.resize(m+7); p.resize(m+7);
for(int i = 0; i<m; i++){
cin>>b[i]>>p[i];
mp[b[i]].insert(p[i]);
}
// exit(0);
g.resize(n+7);
mark.resize(n+7);
// exit(0);
for(int i = 0; i<n; i++){
for(auto& el: mp[i]){
int k = 1;
for(int j = i+el; j<n; j+=el){
g[i].push_back(make_pair(j, k));
k++;
}
k=1;
for(int j = i-el; j>=0; j-=el){
g[i].push_back(make_pair(j, k));
k++;
}
}
}
vector<long long>res = distance(g,0);
debugc(res)
// exit(0);
int ans = res[b[1]];
if(ans == inf){
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;
}
