#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; }