//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan (@iamsazidh)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define file(); freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#define debug(...)
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__);
template <class X, class Y>
ostream& operator<<(ostream& os, const pair<X, Y>& p) {
return os << "(" << p.first << ", " << p.second << ")";
}
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& os, const Container& x) {
int i = 0, n = distance(x.begin(), x.end());
os << "{ ";
for (const auto& y : x)
os << y << (++i < n ? ", " : "");
return os << " }";
}
template <typename... Args>
void _debug(const char* names, Args&&... args) {
string_view s(names);
cerr << "{ ";
size_t i = 0, cnt = 0, n = sizeof...(args);
auto next = [&]() {
while (i < s.size() && (s[i] == ' ' || s[i] == ',')) ++i;
size_t st = i;
while (i < s.size() && s[i] != ',') ++i;
return s.substr(st, i - st);
};
((cerr << next() << ": " << args << (++cnt < n ? ", " : "")), ...);
cerr << " }" << '\n';
}
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
const double EPS = 1e-6;
const int MAXN = 2e3+10;
const ll UNVISITED = 1LL<<61;
vii adj(MAXN);
bitset<MAXN> visited;
vector<vl> cost(MAXN, vl(MAXN, UNVISITED));
bool solve(){
int n, m; cin >> n >> m;
queue<pll> que; // ff = piller no, ss = move
int st, stp; cin >> st >> stp;
adj[st].push_back(stp);
que.push({st, stp});
cost[st][stp] = 0;
int end, endp; cin >> end >> endp;
adj[end].push_back(endp);
for(int i = 0; i < m-2; i++){
int b, p; cin >> b >> p;
adj[b].push_back(p);
}
while(!que.empty()){
auto [b, p] = que.front(); que.pop();
int to = b+p;
if(to<n){
if(!visited[to]){
visited[to] = 1;
for(auto x: adj[to]){
if(cost[to][x]>cost[b][p]+1){
cost[to][x] = cost[b][p] + 1; que.push({to, x});
}
}
}
if(cost[to][p]>cost[b][p]+1) { cost[to][p] = cost[b][p] + 1; que.push({to, p}); }
}
to = b-p;
if(to>=0){
if(!visited[to]){
visited[to] = 1;
for(auto x: adj[to]){
if(cost[to][x]>cost[b][p]+1){
cost[to][x] = cost[b][p] + 1; que.push({to, x});
}
}
}
if(cost[to][p]>cost[b][b]+1) { cost[to][p] = cost[b][p] + 1; que.push({to, p}); }
}
}
ll ans = *min_element(all(cost[end]));
if(ans==UNVISITED) cout << -1 << endl;
else cout << ans << endl;
return 1;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int testcase = 1;
//cin >> testcase;
for(int tc = 1; tc <= testcase; tc++){
//cerr << "TESTCASE - " << tc << endl;
solve();
//cout << (solve() ? "YES" : "NO") << '\n';
cerr << endl;
}
return 0;
}
