Iahub got lost in a very big desert. The desert can be represented as a n × n square matrix, where each cell is a zone of the desert. The cell (i, j) represents the cell at row i and column j (1 ≤ i, j ≤ n). Iahub can go from one cell (i, j) only down or right, that is to cells (i + 1, j) or (i, j + 1). 

Also, there are m cells that are occupied by volcanoes, which Iahub cannot enter. 

Iahub is initially at cell (1, 1) and he needs to travel to cell (n, n). Knowing that Iahub needs 1 second to travel from one cell to another, find the minimum time in which he can arrive in cell (n, n).

Input

The first line contains two integers n (1 ≤ n ≤ 109) and m (1 ≤ m ≤ 105). Each of the next m lines contains a pair of integers, x and y (1 ≤ x, y ≤ n), representing the coordinates of the volcanoes.

Consider matrix rows are numbered from 1 to n from top to bottom, and matrix columns are numbered from 1 to n from left to right. There is no volcano in cell (1, 1). No two volcanoes occupy the same location. 

Output

Print one integer, the minimum time in which Iahub can arrive at cell (n, n). If no solution exists (there is no path to the final cell), print -1.

Examples

Input

4 2
1 3
1 4


Output

6


Input

7 8
1 6
2 6
3 5
3 6
4 3
5 1
5 2
5 3


Output

12


Input

2 2
1 2
2 1


Output

-1

Note

Consider the first sample. A possible road is: (1, 1) →  (1, 2) →  (2, 2) →  (2, 3) →  (3, 3) →  (3, 4) →  (4, 4).
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline T max1(T a, T b, T c) {
  return max1(max1(a, b), c);
}
template <class T>
inline T max1(T a, T b, T c, T d) {
  return max1(max1(a, b, c), d);
}
template <class T>
inline T max1(T a, T b, T c, T d, T e) {
  return max1(max1(a, b, c, d), e);
}
template <class T>
inline T min1(T a, T b) {
  return a < b ? a : b;
}
template <class T>
inline T min1(T a, T b, T c) {
  return min1(min1(a, b), c);
}
template <class T>
inline T min1(T a, T b, T c, T d) {
  return min1(min1(a, b, c), d);
}
template <class T>
inline T min1(T a, T b, T c, T d, T e) {
  return min1(min1(a, b, c, d), e);
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 201000;
int n, m;
int can[maxn][2];
map<int, vector<int> > mp;
vector<pair<int, int> > seg[maxn];
int y[maxn];
int lseg;
int ldp[2];
pair<int, int> dp[2][maxn];
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    mp[a].push_back(b);
  }
  map<int, vector<int> >::iterator it = mp.begin();
  for (; it != mp.end(); it++, lseg++) {
    sort(it->second.begin(), it->second.end());
    int last = 0;
    it->second.push_back(n);
    for (int i = 0; i < (int)it->second.size(); i++) {
      if (it->second[i] > last)
        seg[lseg].push_back(make_pair(last, it->second[i] - 1));
      last = it->second[i] + 1;
    }
    y[lseg] = it->first;
  }
  seg[lseg].push_back(make_pair(n - 1, n - 1));
  y[lseg++] = n;
  int now = 0, nxt = 1;
  ldp[0] = 1;
  if (y[0] != 0)
    dp[0][0] = make_pair(0, n - 1);
  else
    dp[0][0] = seg[0][0];
  for (int i = 0; i < lseg; i++) {
    if (i && y[i] > y[i - 1] + 1 && ldp[now]) {
      ldp[now] = 1;
      dp[now][0].second = n - 1;
    }
    ldp[nxt] = 0;
    for (int link1 = 0, link2 = 0;
         link1 < ldp[now] && link2 < (int)seg[i].size();) {
      pair<int, int> a;
      a.first = max(seg[i][link2].first, dp[now][link1].first);
      a.second = seg[i][link2].second;
      if (dp[now][link1].second >= seg[i][link2].first &&
          dp[now][link1].first <= seg[i][link2].second)
        if (a.first <= a.second) dp[nxt][ldp[nxt]++] = a;
      if (dp[now][link1].second < seg[i][link2].second)
        link1++;
      else
        link2++;
    }
    swap(now, nxt);
  }
  if (ldp[now])
    printf("%d\n", 2 * (n - 1));
  else
    printf("-1\n");
  return 0;
}
