#include <bits/stdc++.h>
struct QEntry
{
int building;
int doge;
int cost;
};
bool visited[30000][30000];
int main()
{
int numBuildings, numDoges;
std::cin >> numBuildings;
std::cin >> numDoges;
std::vector<std::vector<int>> dogesInBuildings(numBuildings);
std::vector<int> dogePositions(numDoges);
std::vector<int> dogePowers(numDoges);
for (int i = 0; i < numDoges; i++)
{
std::cin >> dogePositions[i];
std::cin >> dogePowers[i];
dogesInBuildings[dogePositions[i]].push_back(i);
}
std::deque<QEntry> q;
q.push_back(QEntry { dogePositions[0], 0, 0 });
while (!q.empty())
{
QEntry entry = q.front();
q.pop_front();
if (visited[entry.building][entry.doge])
continue;
if (entry.doge == 1)
{
std::cout << entry.cost << std::endl;
return 0;
}
visited[entry.building][entry.doge] = true;
for (int d : dogesInBuildings[entry.building])
{
if (visited[entry.building][d])
continue;
q.push_front(QEntry { entry.building, d, entry.cost });
}
int pBuilding = entry.building - dogePowers[entry.doge];
if (pBuilding >= 0 && !visited[pBuilding][entry.doge])
{
q.push_back(QEntry { pBuilding, entry.doge, entry.cost + 1 });
}
int nBuilding = entry.building + dogePowers[entry.doge];
if (nBuilding < numBuildings && !visited[nBuilding][entry.doge])
{
q.push_back(QEntry { nBuilding, entry.doge, entry.cost + 1 });
}
}
std::cout << "-1" << std::endl;
}
