题目描述

对于一个长度为 $n$ 的数列 $h=\{h_1,h_2,\dots,h_n\}$，满足 $\forall i\in[1,n),|h_i-h_{i+1}|\le1$。

给出数列中 $m$ 个数，试构造出一个合法完整数列，使得 $\max\{h_1,h_2,\dots,h_n\}$ 最大。

若不存在一个合法的构造方案，请输出 IMPOSSIBLE。

输入格式

第一行，两个整数 $n$ 和 $m$。

接下来 $m$ 行，第 $i+1$ 行两个数 $d_i$ 和 $h_{d_i}$。

数据保证数列 $d=\{d_1,d_2,\dots,d_m\}$ 单调递增。

输出格式

• 若存在合法方案，输出一行一个整数表示最大的 $\max\{h_1,h_2,\dots,h_n\}$；
• 若不存在一个合法方案，请输出 IMPOSSIBLE。

数据范围与约定

对于所有数据，满足 $1\le d_i\le n\le10^8$，$1\le m\le10^5$，$1\le h_{d_i}\le 10^8$。

说明/提示

• 对于第一个样例，存在一个合法构造方案 $h=\{0,0,1,2,1,1,0,1\}$ 使得最大值为 $2$，可以证明不存在一个合法构造方案使得最大值大于此种构造方案；
• 对于第二个样例，$i=7$ 时不满足 $\forall i\in[1,n),|h_i-h_{i+1}|\le1$，故输出 IMPOSSIBLE。

---

### 题目描述

对于一个长度为 $n$ 的数列 $h=\{h_1,h_2,\dots,h_n\}$，满足 $\forall i\in[1,n),|h_i-h_{i+1}|\le1$。

给出数列中 $m$ 个数，试构造出一个合法完整数列，使得 $\max\{h_1,h_2,\dots,h_n\}$ 最大。

若不存在一个合法的构造方案，请输出 `IMPOSSIBLE`。

### 输入格式

第一行，两个整数 $n$ 和 $m$。

接下来 $m$ 行，第 $i+1$ 行两个数 $d_i$ 和 $h_{d_i}$。

数据保证数列 $d=\{d_1,d_2,\dots,d_m\}$ 单调递增。

### 输出格式

- 若存在合法方案，输出一行一个整数表示最大的 $\max\{h_1,h_2,\dots,h_n\}$；
- 若不存在一个合法方案，请输出 `IMPOSSIBLE`。

### 数据范围与约定

对于所有数据，满足 $1\le d_i\le n\le10^8$，$1\le m\le10^5$，$1\le h_{d_i}\le 10^8$。

### 说明/提示

- 对于第一个样例，存在一个合法构造方案 $h=\{0,0,1,2,1,1,0,1\}$ 使得最大值为 $2$，可以证明不存在一个合法构造方案使得最大值大于此种构造方案；
- 对于第二个样例，$i=7$ 时不满足 $\forall i\in[1,n),|h_i-h_{i+1}|\le1$，故输出 `IMPOSSIBLE`。