CF538C.Tourist's Notes

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 h__i. 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 |h__i - h__i + 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 |h__i - h__i + 1| ≤ 1.

一名游客沿山脉徒步旅行。此次徒步持续了 $n$ 天，每天游客都记录下当日海拔高度。第 $i$ 天的高度为某个整数 $h_i$。游客选择了一条足够平缓的路线，即任意连续两天之间的高度变化至多为 $1$，也就是说，对所有 $i$（$1 \le i \le n-1$），均满足不等式 $|h_i - h_{i+1}| \le 1$。

在路线终点，游客乘橡皮筏沿山间河流漂流而下，日记中部分记录被水冲走。此外，剩余记录中的数字也可能发生了失真。现在游客想知道：他整个徒步过程中可能达到的最高海拔是多少？请你帮他恢复出整个徒步过程中可能的最大高度值；或者判断：这些记录失真过于严重，已无法对应任何满足约束 $|h_i - h_{i+1}| \le 1$ 的合法高度序列。

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 d__i and h__d__i (1 ≤ d__i ≤ n, 0 ≤ h__d__i ≤ 108) — the number of the day when the i-th note was made and height on the d__i-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: d__i < d__i + 1.

第一行包含两个以空格分隔的数字 $n$ 和 $m$（$1 \leq n \leq 10^8$，$1 \leq m \leq 10^5$）——分别表示徒步旅行的天数和日记中遗留的笔记数量。

接下来的 $m$ 行每行包含两个以空格分隔的整数 $d_i$ 和 $h_{d_i}$（$1 \leq d_i \leq n$，$0 \leq h_{d_i} \leq 10^8$）——表示第 $i$ 条笔记记录的日期以及该日 $d_i$ 的海拔高度。保证这些笔记按时间顺序给出，即对所有 $i$（从 $1$ 到 $m-1$），均满足 $d_i < d_{i+1}$。

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).

如果这些记录不矛盾，则输出一个整数——整条路线中可能的最大高度值。

如果这些记录与任何一组高度都不相符，则输出一个单词 'IMPOSSIBLE'（不带引号）。

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 _h_7 and _h_8 does not hold, thus the information is inconsistent.

对于第一个样例，一个最大高度为 2 的正确高度序列示例如下：$(0,\,0,\,1,\,2,\,1,\,1,\,0,\,1)$。

在第二个样例中，$h_7$ 与 $h_8$ 之间的不等式关系不成立，因此该信息是矛盾的。