#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
int pow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res *= x;
    y >>= 1;
    x *= x;
  }
  return res;
}
struct Compare {
  constexpr bool operator()(
      pair<long long, pair<long long, long long>> const &a,
      pair<long long, pair<long long, long long>> const &b) const noexcept {
    return a.first < b.first ||
           (a.first == b.first && a.second.first > b.second.first);
  }
};
void prefix_function(string second, long long arr[]) {
  long long border = 0;
  arr[0] = 0;
  for (long long i = 1; i < second.size(); i++) {
    while (border > 0 && second[i] != second[border]) border = arr[border - 1];
    if (second[i] == second[border])
      border++;
    else
      border = 0;
    arr[i] = border;
  }
}
long long mod = 998244353;
long long add(long long a, long long b) {
  return (((a % mod) + (b % mod)) % mod);
}
long long mul(long long a, long long b) {
  return (((a % mod) * (b % mod)) % mod);
}
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
long long subs(long long a, long long b) {
  return (((a % mod) - (b % mod) + mod) % mod);
}
long long dv(long long a, long long b) {
  long long inv = binpow(b, mod - 2);
  return mul(a, inv);
}
long long dsu_arr[100000];
long long dsu_sz[100000];
void dsu(long long n) {
  for (long long i = 0; i <= n; i++) {
    dsu_arr[i] = i;
    dsu_sz[i] = 1;
  }
}
long long find(long long x) {
  long long root = x;
  while (root != dsu_arr[root]) {
    root = dsu_arr[root];
  }
  while (x != dsu_arr[x]) {
    dsu_arr[x] = root;
    x = dsu_arr[x];
  }
  return root;
}
long long merge(long long x, long long y) {
  long long root1 = find(x);
  long long root2 = find(y);
  if (root1 == root2) return 0ll;
  if (dsu_sz[x] > dsu_sz[y]) {
    dsu_arr[root2] = root1;
    dsu_sz[root1] += dsu_sz[root2];
  } else {
    dsu_sz[root2] += dsu_sz[root1];
    dsu_arr[root1] = root2;
  }
  return 1ll;
}
long long n, d;
vector<pair<long long, long long>> sura;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> d;
  long long ans = -1;
  for (long long i = 0; i < d; i++) {
    long long u, v;
    cin >> u >> v;
    sura.push_back({u, v});
    ans = max(ans, v);
  };
  bool hbe = true;
  for (long long i = 1; i < d; i++) {
    if (sura[i].first - sura[i - 1].first <
        abs(sura[i - 1].second - sura[i].second)) {
      hbe = false;
      break;
    }
  }
  if (!hbe) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  for (long long i = 0; i <= d; i++) {
    if (i == d) {
      long long days = n - sura[i - 1].first;
      long long x = sura[i - 1].second + days;
      ans = max(x, ans);
    } else if (i == 0) {
      long long days = sura[i].first - 1;
      long long x = sura[i].second + days;
      ans = max(x, ans);
    } else {
      long long prev = sura[i - 1].second;
      long long next = sura[i].second;
      long long ac_days = sura[i].first - sura[i - 1].first;
      long long baal = abs(prev - next);
      long long x = max(prev, next) + ((ac_days - baal) / 2);
      ans = max(ans, x);
    }
  }
  cout << ans << endl;
}

### Prompt

Please create a solution in cpp to the following problem:

A tourist hiked along the mountain range. The hike lasted for n days, during each day the tourist noted height above the sea level. On the i-th day height was equal to some integer hi. The tourist pick smooth enough route for his hike, meaning that the between any two consecutive days height changes by at most 1, i.e. for all i's from 1 to n - 1 the inequality |hi - hi + 1| ≤ 1 holds.

At the end of the route the tourist rafted down a mountain river and some notes in the journal were washed away. Moreover, the numbers in the notes could have been distorted. Now the tourist wonders what could be the maximum height during his hike. Help him restore the maximum possible value of the maximum height throughout the hike or determine that the notes were so much distorted that they do not represent any possible height values that meet limits |hi - hi + 1| ≤ 1.

Input

The first line contains two space-separated numbers, n and m (1 ≤ n ≤ 108, 1 ≤ m ≤ 105) — the number of days of the hike and the number of notes left in the journal.

Next m lines contain two space-separated integers di and hdi (1 ≤ di ≤ n, 0 ≤ hdi ≤ 108) — the number of the day when the i-th note was made and height on the di-th day. It is guaranteed that the notes are given in the chronological order, i.e. for all i from 1 to m - 1 the following condition holds: di < di + 1.

Output

If the notes aren't contradictory, print a single integer — the maximum possible height value throughout the whole route.

If the notes do not correspond to any set of heights, print a single word 'IMPOSSIBLE' (without the quotes).

Examples

Input

8 2
2 0
7 0


Output

2


Input

8 3
2 0
7 0
8 3


Output

IMPOSSIBLE

Note

For the first sample, an example of a correct height sequence with a maximum of 2: (0, 0, 1, 2, 1, 1, 0, 1).

In the second sample the inequality between h7 and h8 does not hold, thus the information is inconsistent.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
int pow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res *= x;
    y >>= 1;
    x *= x;
  }
  return res;
}
struct Compare {
  constexpr bool operator()(
      pair<long long, pair<long long, long long>> const &a,
      pair<long long, pair<long long, long long>> const &b) const noexcept {
    return a.first < b.first ||
           (a.first == b.first && a.second.first > b.second.first);
  }
};
void prefix_function(string second, long long arr[]) {
  long long border = 0;
  arr[0] = 0;
  for (long long i = 1; i < second.size(); i++) {
    while (border > 0 && second[i] != second[border]) border = arr[border - 1];
    if (second[i] == second[border])
      border++;
    else
      border = 0;
    arr[i] = border;
  }
}
long long mod = 998244353;
long long add(long long a, long long b) {
  return (((a % mod) + (b % mod)) % mod);
}
long long mul(long long a, long long b) {
  return (((a % mod) * (b % mod)) % mod);
}
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}
long long subs(long long a, long long b) {
  return (((a % mod) - (b % mod) + mod) % mod);
}
long long dv(long long a, long long b) {
  long long inv = binpow(b, mod - 2);
  return mul(a, inv);
}
long long dsu_arr[100000];
long long dsu_sz[100000];
void dsu(long long n) {
  for (long long i = 0; i <= n; i++) {
    dsu_arr[i] = i;
    dsu_sz[i] = 1;
  }
}
long long find(long long x) {
  long long root = x;
  while (root != dsu_arr[root]) {
    root = dsu_arr[root];
  }
  while (x != dsu_arr[x]) {
    dsu_arr[x] = root;
    x = dsu_arr[x];
  }
  return root;
}
long long merge(long long x, long long y) {
  long long root1 = find(x);
  long long root2 = find(y);
  if (root1 == root2) return 0ll;
  if (dsu_sz[x] > dsu_sz[y]) {
    dsu_arr[root2] = root1;
    dsu_sz[root1] += dsu_sz[root2];
  } else {
    dsu_sz[root2] += dsu_sz[root1];
    dsu_arr[root1] = root2;
  }
  return 1ll;
}
long long n, d;
vector<pair<long long, long long>> sura;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> d;
  long long ans = -1;
  for (long long i = 0; i < d; i++) {
    long long u, v;
    cin >> u >> v;
    sura.push_back({u, v});
    ans = max(ans, v);
  };
  bool hbe = true;
  for (long long i = 1; i < d; i++) {
    if (sura[i].first - sura[i - 1].first <
        abs(sura[i - 1].second - sura[i].second)) {
      hbe = false;
      break;
    }
  }
  if (!hbe) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  for (long long i = 0; i <= d; i++) {
    if (i == d) {
      long long days = n - sura[i - 1].first;
      long long x = sura[i - 1].second + days;
      ans = max(x, ans);
    } else if (i == 0) {
      long long days = sura[i].first - 1;
      long long x = sura[i].second + days;
      ans = max(x, ans);
    } else {
      long long prev = sura[i - 1].second;
      long long next = sura[i].second;
      long long ac_days = sura[i].first - sura[i - 1].first;
      long long baal = abs(prev - next);
      long long x = max(prev, next) + ((ac_days - baal) / 2);
      ans = max(ans, x);
    }
  }
  cout << ans << endl;
}

```