一名游客沿着山脉徒步旅行。这次徒步旅行持续了 n 天,每天游客都会记录海拔高度。在第 i 天,身高等于某个整数 hi。游客选择足够平滑的路线进行徒步旅行,这意味着任何连续两天之间的高度最多变化 1,即对于所有 i 从 1 到 n - 1 的不等式 |hi - hi + 1| ≤ 1 成立。
在路线的尽头,游客沿着一条山河漂流而下,日记中的一些笔记被冲走了。此外,注释中的数字可能被扭曲。现在这位游客想知道他徒步旅行时的最大高度是多少。帮助他恢复整个徒步旅行中最大高度的最大可能值,或者确定音符严重扭曲以至于它们不代表任何满足限制 |hi - hi + 1| 的可能高度值。 ≤ 1。
输入
第一行包含两个以空格分隔的数字 n 和 m (1 ≤ n ≤ 108, 1 ≤ m ≤ 105) - 徒步旅行的天数和日记中留下的笔记数量。
接下来的 m 行包含两个以空格分隔的整数 di 和 hdi (1 ≤ di ≤ n, 0 ≤ hdi ≤ 108) - 第 i 个音符发出的日期和第 di 天的高度。保证注释按时间顺序给出,即对于从 1 到 m - 1 的所有 i,满足以下条件:di < di + 1。
输出
如果注释不矛盾,则打印一个整数 - 整个路线的最大可能高度值。
如果注释不对应于任何一组高度,则打印一个单词“IMPOSSIBLE”(不带引号)。
示例
输入 #1
8 2 2 0 7 0
输出 #1
2
输入 #2
8 3 2 0 7 0 8 3
输出 #2
IMPOSSIBLE
注意
对于第一个示例,最大为 2 的正确高度序列的示例:(0, 0, 1, 2, 1, 1, 0, 1)。
在第二个样本中,h7 和 h8 之间的不等式不成立,因此信息不一致。