#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i = 0; i < n; i++)
typedef long long ll;
const ll INF = (ll)1e13;
const int MAXN = 10, MAXM = 3;
int N, M;
int B[MAXM], P[MAXM];
map<vector<int>, ll> dist;
priority_queue<tuple<ll, vector<int>>> pq;
ll solve()
{
vector<int> init_state;
REP(i, M)
init_state.push_back(B[i]);
init_state.push_back(0);
dist[init_state] = 0;
pq.emplace(0, init_state);
while (!pq.empty())
{
ll d;
vector<int> state;
tie(d, state) = pq.top();
pq.pop();
if (-d > dist[state])
continue;
int doge = state.back();
if (doge == 1)
return -d;
// move
for (int sign = -1; sign <= 1; sign += 2)
{
vector<int> new_state = state;
int new_building = new_state[doge] + sign * P[doge];
if (new_building < 0 || new_building >= N)
continue;
new_state[doge] = new_building;
if (!dist.count(new_state) || dist[new_state] > dist[state] + 1)
{
dist[new_state] = dist[state] + 1;
pq.emplace(-dist[new_state], new_state);
}
}
// pass news
REP(new_doge, M) if (new_doge != doge && state[new_doge] == state[doge])
{
vector<int> new_state = state;
new_state[M] = new_doge;
if (!dist.count(new_state) || dist[new_state] > dist[state])
{
dist[new_state] = dist[state];
pq.emplace(-dist[new_state], new_state);
}
}
}
return -1;
}
int main()
{
cin >> N >> M;
REP(i, M)
cin >> B[i] >> P[i];
cout << solve() << endl;
}
