#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <set> using namespace std; const int MAX_M = 30000; int dist0[MAX_M]; struct doge { int p; }; bool operator < (doge X, doge Y) { if(dist0[X.p] == dist0[Y.p]) return X.p < Y.p; return dist0[X.p] < dist0[Y.p]; } int main() { int N, M; cin >> N >> M; int B[M], P[M]; vector<int> doge_pos[N]; for(int i = 0; i < M; i++) { cin >> B[i] >> P[i]; doge_pos[ B[i] ].push_back(i); } dist0[0] = 0; for(int i = 1; i < M; i++) dist0[i] = 2000000000; set<doge> dogeset; for(int i = 0; i < M; i++) dogeset.insert(doge{i}); while(!dogeset.empty()) { doge g = *dogeset.begin(); dogeset.erase(g); int i = g.p; for(int v = B[i] % P[i]; v < N; v += P[i]) for(int j: doge_pos[v]) if(i != j) { int weight = abs((B[j] - B[i]) / P[i]); if (dist0[j] > dist0[i] + weight) { dogeset.erase(doge{j}); dist0[j] = dist0[i] + weight; dogeset.insert(doge{j}); } } } if(dist0[1] == 2000000000) cout << "-1\n"; else cout << dist0[1] << '\n'; return 0; }