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.


-----Input-----

The first line contains two space-separated numbers, n and m (1 ≤ n ≤ 10^8, 1 ≤ m ≤ 10^5) — 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} ≤ 10^8) — 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.


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

Difficulty: MEDIUM_HARD
Tags: Sorting

Implementation

Greedy algorithms

Complete search

Mathematics
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
(n, m) = list(map(int, input().split(' ')))
d = []
for i in range(m):
	d.append(list(map(int, input().split(' '))))
ispossible = True
maxheights = []
maxheights.append(d[0][1] + d[0][0] - 1)
maxheights.append(d[-1][1] + n - d[-1][0])
for i in range(m - 1):
	d1 = d[i]
	d2 = d[i + 1]
	if abs(d2[1] - d1[1]) > d2[0] - d1[0]:
		ispossible = False
	maxheights.append((d1[1] + d2[1] + d2[0] - d1[0]) // 2)
if ispossible:
	print(max(maxheights))
else:
	print('IMPOSSIBLE')


(n, m) = map(int, input().split())
(d, h) = ([], [])
for i in range(m):
	(di, hi) = map(int, input().split())
	d.append(di)
	h.append(hi)
maximum = h[0]
if d[0] != 1:
	d.insert(0, 1)
	h.insert(0, -1)
	m += 1
flag = 0
for i in range(1, m):
	diff = d[i] - d[i - 1]
	if h[i - 1] == -1:
		if diff + h[i] > maximum:
			maximum = diff + h[i]
	elif abs(h[i] - h[i - 1]) > diff:
		flag = 1
		break
	elif abs(h[i] - h[i - 1]) < diff:
		p = diff - abs(h[i - 1] - h[i])
		if max(h[i], h[i - 1]) + p // 2 > maximum:
			maximum = p // 2 + max(h[i], h[i - 1])
	elif max(h[i], h[i - 1]) > maximum:
		maximum = max(h[i], h[i - 1])
if d[m - 1] < n:
	if maximum < h[m - 1] + n - d[m - 1]:
		maximum = h[m - 1] + n - d[m - 1]
if flag == 1:
	print('IMPOSSIBLE')
else:
	print(maximum)


def isOk(a0, a1):
	(i0, h0) = a0
	(i1, h1) = a1
	if h1 < h0:
		return isOk((i0, h1), (i1, h0))
	else:
		return i1 - i0 >= h1 - h0

def getMaxHeight(a0, a1):
	(i0, h0) = a0
	(i1, h1) = a1
	d = h1 - h0
	s = i1 - i0
	if h1 < h0:
		return getMaxHeight((i0, h1), (i1, h0))
	elif h0 < h1:
		return getMaxHeight((i0 + d, h0 + d), (i1, h1))
	else:
		return h0 + s // 2

def getMax1Height(a):
	(i0, h0) = a
	return h0 + i0 - 1

def getMaxNHeight(n, a):
	(i0, h0) = a
	return h0 + (n - i0)
s = input()
hlist = list()
[n, m] = list(map(int, s.split(' ')))
for i in range(0, m):
	s = input()
	[b, h] = list(map(int, s.split(' ')))
	hlist.append((b, h))
iscan = True
for i in range(1, m):
	if not isOk(hlist[i - 1], hlist[i]):
		iscan = False
		break
if iscan == False:
	print('IMPOSSIBLE')
else:
	res = getMax1Height(hlist[0])
	res = max(res, getMaxNHeight(n, hlist[m - 1]))
	for i in range(1, m):
		res = max(res, getMaxHeight(hlist[i - 1], hlist[i]))
	print(res)


(n, m) = map(int, input().split())
(prevd, prevh) = map(int, input().split())
maxi = prevd - 1 + prevh
check = 0
for i in range(m - 1):
	(d, h) = map(int, input().split())
	if d - prevd >= abs(prevh - h):
		k = (d - prevd - abs(prevh - h)) // 2
		if maxi < max(prevh + k, h + k):
			maxi = max(prevh + k, h + k)
		(prevd, prevh) = (d, h)
	else:
		check = 1
		break
if check:
	print('IMPOSSIBLE')
elif maxi >= prevh + n - prevd:
	print(maxi)
else:
	print(prevh + n - prevd)


(N, M) = list(map(int, input().split()))
H = []
D = []
for i in range(M):
	(d, h) = list(map(int, input().split()))
	H.append(h)
	D.append(d)
res = max(max(H), H[M - 1] + N - D[M - 1])
res = max(res, H[0] + D[0] - 1)
for i in range(M - 1):
	dest = D[i + 1] - D[i]
	diff = abs(H[i + 1] - H[i])
	if diff > dest:
		res = float('inf')
		break
	else:
		res = max(res, (dest - diff) // 2 + max(H[i + 1], H[i]))
if res == float('inf'):
	print('IMPOSSIBLE')
else:
	print(res)


from os import path
import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def read():
	sys.stdin = open('input1.txt', 'r')
	sys.stdout = open('output1.txt', 'w')

def powermod(a, b, m):
	a %= m
	res = 1
	if a == 0:
		return 0
	while b > 0:
		if b & 1:
			res = res * a % m
		b = b >> 1
		a = a * a % m
	return res

def isprime(n):
	if n <= 1:
		return 0
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return 0
	return 1

def solve():
	(n, m) = mi()
	a = []
	for i in range(m):
		(x, y) = mi()
		a.append([x, y])
	ans = a[0][0] - 1 + a[0][1]
	for i in range(1, m):
		x = a[i][0] - a[i - 1][0] - 1
		y = abs(a[i][1] - a[i - 1][1]) - 1
		ans = max(ans, a[i][1])
		if x < y:
			print('IMPOSSIBLE')
			exit(0)
		x -= y + 1
		if x > 0:
			x1 = ceil(x / 2)
			ans = max(ans, x1 + max(a[i][1], a[i - 1][1]))
	x2 = n - a[m - 1][0] + a[m - 1][1]
	ans = max(ans, x2)
	print(ans)
if path.exists('input.txt'):
	read()
solve()


(n, m) = map(int, input().split())
arr = []
for i in range(m):
	(d, h) = map(int, input().split())
	arr.append([d, h])
arr.sort()
flag = 0
for j in range(m - 1):
	if abs(arr[j][0] - arr[j + 1][0]) < abs(arr[j][1] - arr[j + 1][1]):
		print('IMPOSSIBLE')
		flag = 1
		break
if flag == 0:
	arr1 = []
	arr1.append(arr[0][1] + abs(arr[0][0] - 1))
	arr1.append(arr[-1][1] + abs(arr[-1][0] - n))
	for k in range(m - 1):
		i = abs(arr[k][0] - arr[k + 1][0])
		ex = abs(arr[k][1] - arr[k + 1][1])
		f = abs(i - ex)
		c = f // 2
		arr1.append(max(arr[k][1], arr[k + 1][1]) + c)
	print(max(arr1))


(n, m) = input().split()
n = int(n)
m = int(m)
arr = []
for i in range(m):
	(d, h) = input().split()
	arr.append([int(d), int(h)])
last = arr[0]
res = arr[0][1]
for i in range(1, m):
	if arr[i][0] - last[0] < abs(arr[i][1] - last[1]):
		print('IMPOSSIBLE')
		exit()
	else:
		diff = arr[i][1] - last[1]
		res = max(res, (arr[i][0] - last[0] + diff) // 2 + last[1])
		res = max(res, arr[i][1])
		last = arr[i]
print(max(arr[0][1] + arr[0][0] - 1, max(res, n - arr[len(arr) - 1][0] + arr[len(arr) - 1][1])))


(n, m) = [int(x) for x in input().split()]
d = []
h = []
s = 0
amax = 0
for i in range(m):
	(p, q) = [int(x) for x in input().split()]
	d.append(p)
	h.append(q)
for i in range(m - 1):
	if abs(h[i + 1] - h[i]) / (d[i + 1] - d[i]) > 1:
		print('IMPOSSIBLE')
		s += 1
		break
if s == 0:
	for i in range(m - 1):
		lshift = h[i] - 0
		rshift = h[i + 1] - 0
		a = d[i + 1] + rshift - (d[i] - lshift)
		if a // 2 > amax:
			amax = a // 2
	b = h[0] + d[0] - 1
	c = h[m - 1] + n - d[m - 1]
	if amax >= b and amax >= c:
		print(amax)
	elif b >= amax and b >= c:
		print(b)
	else:
		print(c)


(n, m) = map(int, input().split())
ls = []
for i in range(m):
	(d, h) = map(int, input().split())
	ls.append([d, h])
ls.sort()
max_h = 0
flag = True
max_h = max(max_h, ls[0][0] - 1 + ls[0][1])
max_h = max(max_h, n - ls[m - 1][0] + ls[m - 1][1])
for i in range(m - 1):
	max_h = max(max_h, ls[i][1])
	if ls[i + 1][1] - ls[i][1] > ls[i + 1][0] - ls[i][0] or ls[i][1] - ls[i + 1][1] > ls[i + 1][0] - ls[i][0]:
		flag = False
		break
	else:
		x = (ls[i + 1][1] - ls[i][1] + ls[i + 1][0] - ls[i][0]) // 2
		max_h = max(max_h, x + ls[i][1])
max_h = max(max_h, ls[m - 1][1])
if flag:
	print(max_h)
else:
	print('IMPOSSIBLE')


(n, m) = [int(x) for x in input().split()]
a = []
ans = 0
while m > 0:
	p = [int(x) for x in input().split()]
	a.append(p)
	ans = max(ans, p[1])
	m -= 1
flag = 1
for i in range(len(a) - 1):
	(x, y) = (a[i], a[i + 1])
	t = y[0] - x[0] - 1
	if abs(y[1] - x[1]) > y[0] - x[0]:
		flag = 0
		break
	else:
		ans = max(ans, max(x[1], y[1]) + (y[0] - x[0] - abs(y[1] - x[1])) // 2)
ans = max(ans, a[0][1] + a[0][0] - 1)
ans = max(ans, a[len(a) - 1][1] + (n - a[len(a) - 1][0]))
if flag:
	print(ans)
else:
	print('IMPOSSIBLE')


(n, m) = map(int, input().split())
notes = [list(map(int, input().split())) for _ in range(m)]
if m == 1:
	(d, h) = notes[0]
	print(max(h + (d - 1), h + (n - d)))
	exit(0)
(d0, h0) = notes[0]
ans = h0 + (d0 - 1)
for i in range(m - 1):
	(d1, h1) = notes[i]
	(d2, h2) = notes[i + 1]
	if d2 - d1 < abs(h1 - h2):
		ans = -1
		break
	else:
		ans = max((h1 + h2 + (d2 - d1)) // 2, ans)
else:
	(dm, hm) = notes[m - 1]
	ans = max(ans, hm + (n - dm))
print(ans if ans != -1 else 'IMPOSSIBLE')


import sys
fin = sys.stdin
(n, m) = [int(number) for number in fin.readline().split()]
(d, h) = [int(number) for number in fin.readline().split()]
mx = h + d - 1
for i in range(1, m):
	(ld, lh) = (d, h)
	(d, h) = [int(number) for number in fin.readline().split()]
	c = d - ld - abs(h - lh)
	if c < 0:
		print('IMPOSSIBLE')
		sys.exit()
	cmx = max(h, lh) + c // 2
	mx = max(mx, cmx)
mx = max(mx, h + n - d)
print(mx)


(n, m) = list(map(int, input().split()))
l = []
for i in range(m):
	l.append(list(map(int, input().split())))
ans = max(l[0][1] + l[0][0] - 1, l[-1][1] + n - l[-1][0])
for i in range(m - 1):
	if abs(l[i][1] - l[i + 1][1]) > abs(l[i][0] - l[i + 1][0]):
		ans = 'IMPOSSIBLE'
		break
	if l[i][1] > l[i + 1][1]:
		ans = max(ans, l[i][1] + (l[i + 1][0] - l[i][0] - (l[i][1] - l[i + 1][1])) // 2)
	else:
		ans = max(ans, l[i + 1][1] + (l[i + 1][0] - l[i][0] - (l[i + 1][1] - l[i][1])) // 2)
print(ans)


import os
import sys
import functools
import collections
import itertools

class Solution:

	def __init__(self):
		self.M = 0
		self.N = 0
		self.notes = None

	def readInput(self):
		(self.N, self.M) = [int(x) for x in input().split()]
		self.notes = []
		for i in range(self.M):
			(di, hi) = [int(x) for x in input().split()]
			self.notes.append((di, hi))

	def readMockInput(self):
		pass

	def solve(self):
		if self.notes[0][0] > 1:
			self.notes = [(1, sum(self.notes[0]) - 1)] + self.notes
		if self.notes[-1][0] < self.N:
			self.notes.append((self.N, self.notes[-1][1] + self.N - self.notes[-1][0]))
		res = max([x[1] for x in self.notes])
		for i in range(1, len(self.notes)):
			(d1, h1) = self.notes[i - 1]
			(d2, h2) = self.notes[i]
			if abs(h1 - h2) > abs(d1 - d2):
				print('IMPOSSIBLE')
				return
			res = max(res, (abs(d1 - d2) + h1 + h2) // 2)
		print(res)
s = Solution()
s.readInput()
s.solve()


import sys
(n, m) = map(int, str.split(sys.stdin.readline()))
pd = ph = None
top = None
for _ in range(m):
	(d, h) = map(int, str.split(sys.stdin.readline()))
	if pd is None:
		top = d - 1 + h
	else:
		if pd and d - pd < abs(h - ph):
			print('IMPOSSIBLE')
			exit()
		delta = d - pd - 1 - abs(h - ph)
		top = max(top, max(ph, h) + delta // 2 + delta % 2)
	(pd, ph) = (d, h)
top = max(top, h + n - d)
print(top)


3
import sys
(n, m) = list(map(int, input().split()))
firstData = None
maxHeight = -1
for i in range(m):
	(d, h) = list(map(int, input().split()))
	if firstData is None:
		firstData = (d, h)
	else:
		if d - prevD < abs(h - prevH):
			print('IMPOSSIBLE')
			return
		maxH = max(h, prevH)
		minH = min(h, prevH)
		resource = d - prevD - (maxH - minH)
		possibleH = maxH + resource // 2
		maxHeight = max(maxHeight, possibleH)
	(prevD, prevH) = (d, h)
	lastData = (d, h)
maxHeight = max(maxHeight, firstData[1] + firstData[0] - 1)
maxHeight = max(maxHeight, lastData[1] + (n - lastData[0]))
print(maxHeight)


(n, m) = map(int, input().split())
main = []
for i in range(m):
	(d, h) = map(int, input().split())
	main.append((d, h))
(s, e) = (False, False)
for (d, h) in main:
	if d == 1:
		s = True
	elif d == n:
		e = True
start = []
if not s:
	start.append((0, main[0][0] - 1 + main[0][1]))
if not e:
	start.append((n, n - main[-1][0] + main[-1][1]))
main = main + start
main.sort()
(cd, ch) = (main[0][0], main[0][1])
currmax = main[0][1]
for (d, h) in main[1:]:
	if d - cd < abs(h - ch):
		currmax = 'IMPOSSIBLE'
		break
	currmax = max(currmax, (d - cd + h + ch) // 2)
	cd = d
	ch = h
print(currmax)


import sys
input = sys.stdin.readline

def judge(d, hs, he, x):
	return 2 * x - hs - he <= d

def binary_search(d, hs, he):
	(l, r) = (max(hs, he), 10 ** 10)
	while l <= r:
		mid = (l + r) // 2
		if judge(d, hs, he, mid):
			l = mid + 1
		else:
			r = mid - 1
	return r
(n, m) = map(int, input().split())
dh = [tuple(map(int, input().split())) for _ in range(m)]
ans = dh[0][1] + dh[0][0] - 1
for i in range(m - 1):
	(di, hi) = dh[i]
	(dj, hj) = dh[i + 1]
	if abs(hi - hj) > abs(di - dj):
		print('IMPOSSIBLE')
		exit()
	ans = max(ans, binary_search(dj - di, hi, hj))
ans = max(ans, dh[-1][1] + n - dh[-1][0])
print(ans)


(n, m) = list(map(int, input().split()))
max_height = 0
(prev_d, prev_h) = [0, 0]
for i in range(m):
	(d, h) = list(map(int, input().split()))
	if i == 0:
		max_height = d - 1 + h
		prev_d = d
		prev_h = h
		if i == m - 1:
			max_height = max(max_height, n - d + h)
		continue
	intersection = (-1 * (prev_d - prev_h) + (d + h)) / 2
	day = intersection - prev_h + prev_d
	if day > d or day < prev_d:
		max_height = -1
		break
	max_height = max(max_height, int(intersection))
	if i == m - 1:
		max_height = max(max_height, n - d + h)
	prev_d = d
	prev_h = h
if max_height >= 0:
	print(max_height)
else:
	print('IMPOSSIBLE')


from sys import stdin
input = stdin.readline
(n, m) = (int(x) for x in input().split())
(pd, ph) = (int(x) for x in input().split())
res = ph + pd - 1
for i in range(1, m):
	(d, h) = (int(x) for x in input().split())
	dd = d - pd
	dh = abs(h - ph)
	if dd < dh:
		print('IMPOSSIBLE')
		exit()
	dd -= dh
	res = max(res, max(ph, h) + dd // 2)
	pd = d
	ph = h
res = max(res, ph + (n - pd))
print(res)


x = input()
(n, m) = x.strip().split(' ')
(n, m) = (int(n), int(m))
x = input()
(d, h) = x.strip().split(' ')
(d, h) = (int(d), int(h))
max_height = h + d - 1
last_day = d
last_height = h
posible = True
for k in range(m - 1):
	x = input()
	(d, h) = x.strip().split()
	(d, h) = (int(d), int(h))
	if d - last_day >= abs(last_height - h):
		mi = max(last_height, h)
		prostih = d - last_day - abs(last_height - h)
		pos_h = mi + prostih // 2
		if pos_h > max_height:
			max_height = pos_h
	else:
		posible = False
	last_day = d
	last_height = h
manjka_dni = n - d
if last_height + manjka_dni > max_height:
	max_height = last_height + manjka_dni
if posible:
	print(max_height)
else:
	print('IMPOSSIBLE')


(n, m) = list(map(int, input().rstrip().split()))
d = []
h = []
flag = 1
for i in range(m):
	(a, b) = list(map(int, input().rstrip().split()))
	d += [a]
	h += [b]
	if i > 0 and abs(d[i] - d[i - 1]) < abs(h[i] - h[i - 1]):
		flag = 0
if flag == 0:
	print('IMPOSSIBLE')
else:
	maxm = 0
	for i in range(m - 1):
		days = d[i + 1] - d[i] - 1
		high = abs(h[i + 1] - h[i])
		days_left = days - high
		maxm = max(maxm, max(h[i], h[i + 1]) + days_left // 2 + days_left % 2)
	diff = d[0] - 1
	maxm = max(maxm, h[0] + diff)
	diff = n - d[m - 1]
	maxm = max(maxm, h[m - 1] + diff)
	print(maxm)


(n, m) = list(map(int, input().split()))
(l_d, l_h) = list(map(int, input().split()))
m_h = l_h + l_d - 1
for i in range(1, m):
	(n_d, n_h) = list(map(int, input().split()))
	if abs(n_h - l_h) > n_d - l_d:
		print('IMPOSSIBLE')
		return
	m_h = max(m_h, max(l_h, n_h) + (n_d - l_d - abs(n_h - l_h)) // 2)
	(l_d, l_h) = (n_d, n_h)
m_h = max(m_h, l_h + n - l_d)
print(m_h)


(n, m) = map(int, input().split())
(l_d, l_h) = map(int, input().split())
m_h = l_h + l_d - 1
for i in range(1, m):
	(n_d, n_h) = map(int, input().split())
	if abs(n_h - l_h) > n_d - l_d:
		print('IMPOSSIBLE')
		exit(0)
	m_h = max(m_h, max(l_h, n_h) + (n_d - l_d - abs(n_h - l_h)) // 2)
	(l_d, l_h) = (n_d, n_h)
m_h = max(m_h, l_h + n - l_d)
print(m_h)


(n, m) = map(int, input().split())
possible = True
(day_prev, h_prev) = map(int, input().split())
h_max = h_prev + (day_prev - 1)
for i in range(m - 1):
	(day, h) = map(int, input().split())
	if abs(h - h_prev) > day - day_prev:
		possible = False
		break
	h_new = max(h, h_prev) + (day - day_prev - abs(h - h_prev)) // 2
	h_max = max(h_max, h_new)
	(day_prev, h_prev) = (day, h)
h_max = max(h_max, h_prev + (n - day_prev))
if possible:
	print(h_max)
else:
	print('IMPOSSIBLE')


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bs(a, l, h, x):
	while l < h:
		mid = (l + h) // 2
		if a[mid] == x:
			return mid
		if a[mid] < x:
			l = mid + 1
		else:
			h = mid
	return l

def sieve(a):
	for i in range(3, 10 ** 6 + 1, 2):
		a[i] = 1
	for i in range(3, 10 ** 6 + 1, 2):
		for j in range(i * i, 10 ** 6 + 1, i):
			a[j] = 0
	a[2] = 1
	return a

def solve():
	(n, m) = sep()
	a = []
	b = []
	for i in range(m):
		(x, y) = sep()
		b.append([x, y])
	for i in range(1, m):
		if b[i][0] - b[i - 1][0] < abs(b[i][1] - b[i - 1][1]):
			print('IMPOSSIBLE')
			return
	ans = 0
	for i in range(1, m):
		gap = b[i][0] - b[i - 1][0]
		temp = abs(b[i][1] - b[i - 1][1])
		ans = max(ans, max(b[i][1], b[i - 1][1]) + (gap - temp) // 2)
	for i in range(m):
		ans = max(ans, b[i][1])
	if b[0][0] != 1:
		ans = max(ans, b[0][1] + (b[0][0] - 1))
	if b[m - 1][0] != n:
		ans = max(ans, b[m - 1][1] + (n - b[m - 1][0]))
	print(ans)
testcase(1)


(n, m) = map(int, input().split())
possible = True
(s, a) = map(int, input().split())
highest = a + s - 1
for i in range(1, m):
	(t, b) = map(int, input().split())
	slack = t - s - abs(a - b)
	if slack < 0:
		possible = False
	else:
		highest = max(highest, max(a, b) + slack // 2)
	(s, a) = (t, b)
highest = max(highest, a + n - s)
print(highest if possible else 'IMPOSSIBLE')


(n, m) = map(int, input().split())
notes = [[int(j) for j in input().split()] for i in range(m)]
ans = max([i[1] for i in notes])
if notes[0][0] != 1:
	ans = max(ans, notes[0][0] - 1 + notes[0][1])
if notes[-1][0] != n:
	ans = max(ans, n - notes[-1][0] + notes[-1][1])
isOk = True
for (a, b) in zip(notes, notes[1:]):
	difference = b[0] - a[0] - 1
	descentNeeded = abs(b[1] - a[1])
	if descentNeeded > difference + 1:
		isOk = False
		break
	x = max(a[1], b[1])
	chng = (difference - descentNeeded + 1) // 2
	ans = max(ans, x + chng)
if not isOk:
	print('IMPOSSIBLE')
else:
	print(ans)


(N, M) = list(map(int, input().split()))
H = []
for i in range(M):
	(d, h) = list(map(int, input().split()))
	H.append((d, h))
best = H[0][0] - 1 + H[0][1]
for i in range(M - 1):
	diffd = H[i + 1][0] - H[i][0]
	diffh = abs(H[i + 1][1] - H[i][1])
	if diffd >= diffh:
		best = max(best, max(H[i + 1][1], H[i][1]) + (diffd - diffh) // 2)
	else:
		print('IMPOSSIBLE')
		break
else:
	best = max(best, H[M - 1][1] + (N - H[M - 1][0]))
	print(best)


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = map(int, input().split())
	d = []
	hd = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		d.append(x)
		hd.append(y)
	for i in range(len(d) - 1):
		if abs(d[i + 1] - d[i]) < abs(hd[i + 1] - hd[i]):
			print('IMPOSSIBLE')
			exit(0)
	ans = 0
	x = d[0]
	y = hd[0]
	ans = max(ans, y + x - 1)
	x = d[-1]
	y = hd[-1]
	ans = max(ans, n - x + y)
	for i in range(len(d) - 1):
		ans = max(ans, (d[i + 1] - d[i] + hd[i + 1] + hd[i]) // 2)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, m) = map(int, input().split())
(d, h) = ([0] * m, [0] * m)
for i in range(m):
	(d[i], h[i]) = map(int, input().split())
(ans, zhi) = (max(h[0] + d[0] - 1, h[m - 1] + n - d[m - 1], max(h)), True)
for i in range(m - 1):
	need = abs(h[i + 1] - h[i]) - 1
	changes = d[i + 1] - d[i] - 1
	if need > changes:
		zhi = False
	if h[i + 1] == h[i]:
		ans = max(ans, h[i] + changes // 2 + changes % 2)
	elif h[i + 1] > h[i]:
		ans = max(ans, h[i] + (changes - need - 2) // 2 + need + (changes - need > 0) + (changes - need > 1))
	elif h[i + 1] < h[i]:
		ans = max(ans, h[i] + (changes - need) // 2)
print(ans if zhi else 'IMPOSSIBLE')


def get(d1, h1, d2, h2):
	d_d = d2 - d1
	if abs(h2 - h1) > d_d:
		return None
	res = (d_d - abs(h2 - h1)) // 2 + max(h1, h2)
	return res
(n, m) = tuple(map(int, input().split()))
l = [(0, 0)] * (m + 1)
for i in range(1, m + 1):
	l[i] = tuple(map(int, input().split()))
maxi = 0
for i in range(1, m):
	tmp = get(l[i][0], l[i][1], l[i + 1][0], l[i + 1][1])
	if tmp == None:
		print('IMPOSSIBLE')
		exit(0)
	if tmp > maxi:
		maxi = tmp
if l[m][1] + n - l[m][0] > maxi:
	maxi = l[m][1] + n - l[m][0]
if l[1][1] + l[1][0] - 1 > maxi:
	maxi = l[1][1] + l[1][0] - 1
print(maxi)


import sys
f = sys.stdin
(n, m) = map(int, f.readline().strip().split())
res = True
for i in range(m):
	(d, h) = map(int, f.readline().strip().split())
	if i == 0:
		maxH = h + (d - 1)
		hpr = h
		dpr = d
	elif abs(h - hpr) > d - dpr:
		res = False
	else:
		dt = d - dpr - (max(hpr, h) - min(hpr, h))
		maxH = max(maxH, max(hpr, h) + dt // 2)
		hpr = h
		dpr = d
maxH = max(maxH, hpr + (n - dpr))
if res:
	print(maxH)
else:
	print('IMPOSSIBLE')


from __future__ import print_function
from collections import *
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m) = gil()
h = [gil() for _ in range(m)]
ans = max(h[0][1], h[-1][1])
for i in range(1, m):
	(xd, yd) = (h[i][0] - h[i - 1][0], abs(h[i][1] - h[i - 1][1]))
	if yd > xd:
		print('IMPOSSIBLE')
		exit()
	ans = max(ans, max(h[i][1], h[i - 1][1]) + (xd - yd) // 2, h[i][1])
ans = max(ans, sum(h[0]) - 1, h[-1][1] - h[-1][0] + n)
print(ans)


(n, m) = map(int, input().split())
(ld, lh) = map(int, input().split())
mh = lh + (ld - 1)
for i in range(1, m):
	(d, h) = map(int, input().split())
	if abs(h - lh) > d - ld:
		print('IMPOSSIBLE')
		exit()
	mh = max(mh, max(h, lh) + (d - ld - abs(h - lh)) // 2)
	(ld, lh) = (d, h)
mh = max(mh, lh + (n - ld))
print(mh)


def maxheight(start, end):
	(start_day, start_height) = start
	(end_day, end_height) = end
	ddays = end_day - start_day
	dheight = end_height - start_height
	xdays = ddays - abs(dheight)
	if xdays < 0:
		return -1
	else:
		return xdays // 2 + max(start_height, end_height)
import sys
data = sys.stdin
days = int(data.readline().split()[0])
entries = []
for l in data.read().splitlines():
	entries.append(tuple(map(int, l.split(' '))))
entries.sort()
maxheights = []
for e in entries:
	maxheights.append(e[1])
for i in range(len(entries) - 1):
	h = maxheight(entries[i], entries[i + 1])
	if h < 0:
		print('IMPOSSIBLE')
		break
	else:
		maxheights.append(h)
else:
	first = entries[0]
	maxheights.append(first[0] - 1 + first[1])
	last = entries[-1]
	maxheights.append(days - last[0] + last[1])
	print(str(max(maxheights)))


(n, m) = [int(x) for x in input().split()]
l = []
h = []
for i in range(m):
	(d, hi) = [int(x) for x in input().split()]
	l.append([d, hi])
	h.append(hi)
jud = 0
for i in range(1, m):
	if abs(l[i][1] - l[i - 1][1]) > l[i][0] - l[i - 1][0]:
		jud = 1
		break
	else:
		d1 = l[i - 1][0]
		d2 = l[i][0]
		h1 = l[i - 1][1]
		h2 = l[i][1]
		hmax = max(h1, h2)
		hmin = min(h1, h2)
		disd = abs(d1 - d2)
		dish = -abs(h1 - h2)
		x = dish + disd
		h.append(int(hmax + (disd + dish) / 2))
if jud == 1:
	print('IMPOSSIBLE')
else:
	h.append(l[0][1] + l[0][0] - 1)
	h.append(l[-1][1] + n - l[-1][0])
	print(max(h))


(n, m) = map(int, input().split())
(res, pd, ph) = (0, 0, 0)
for i in range(m):
	(d, h) = map(int, input().split())
	if i == 0:
		res = h + (d - 1)
	else:
		delta_d = d - pd
		delta_h = abs(h - ph)
		if delta_h > delta_d:
			print('IMPOSSIBLE')
			exit()
		res = max(res, max(h, ph) + (delta_d - delta_h) // 2)
	if i == m - 1:
		res = max(res, h + n - d)
	(pd, ph) = (d, h)
print(res)


__author__ = 'Данила'
(n, m) = map(int, input().split())
l = []
for i in range(m):
	(d, h) = map(int, input().split())
	l.append((d, h))
k = -1
flag = True
for i in range(m - 1):
	b = l[i + 1][1]
	a = l[i][1]
	y = l[i + 1][0]
	x = l[i][0]
	if a + y - x >= b and a - y + x <= b:
		if (y - x - a + b) // 2 >= b - a:
			k1 = (y - x - a + b) // 2 + a
			if k1 > k:
				k = k1
		else:
			k1 = max(a, b)
			if k1 > k:
				k = k1
	else:
		flag = False
b = l[0][0] - 1 + l[0][1]
a = l[-1][1] + n - l[-1][0]
if flag:
	print(max(k, a, b))
else:
	print('IMPOSSIBLE')


def main():
	(n, m) = map(int, input().split())
	(d0, h0) = map(int, input().split())
	res = [h0 + d0 - 1]
	for i in range(m - 1):
		(d1, h1) = map(int, input().split())
		dd = d1 - d0
		if h1 > h0:
			base = h1
			dh = h1 - h0
		else:
			base = h0
			dh = h0 - h1
		if dh > dd:
			print('IMPOSSIBLE')
			return
		res.append(base + (dd - dh) // 2)
		(d0, h0) = (d1, h1)
	res.append(h0 + n - d0)
	print(max(res))
main()


import math

def main():
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	heights = []
	for _ in range(m):
		(x, y) = input().split()
		heights.append([int(x), int(y)])
	if len(heights) == 1:
		(d, h) = heights[0]
		print(max(-1 + d + h, n - d + h))
		return
	maxHeights = []
	(d, h) = heights[0]
	maxHeights.append(-1 + d + h)
	(d, h) = heights[-1]
	maxHeights.append(n - d + h)
	for i in range(len(heights) - 1):
		(d1, h1) = heights[i]
		(d2, h2) = heights[i + 1]
		slope = (h2 - h1) / (d2 - d1)
		if abs(slope) > 1:
			print('IMPOSSIBLE')
			return
		maxHeights.append(math.floor((d2 + h2 + d1 - h1) / 2 - d1 + h1))
	print(max(maxHeights))
main()


(n, m) = map(int, input().split())
ans = 0
h1 = 0
h2 = 0
d1 = 0
d2 = 0
for i in range(m):
	(x, y) = map(int, input().split())
	if i == 0:
		ans = y + x - 1
		h1 = y
		d1 = x
	else:
		h2 = y
		d2 = x
		if h1 > h2:
			(h1, h2) = (h2, h1)
		t1 = h2 + (d2 - d1 - (h2 - h1)) // 2
		if t1 < h2:
			print('IMPOSSIBLE')
			exit()
		ans = max(ans, t1)
		h1 = y
		d1 = x
ans = max(ans, h1 + n - d1)
print(ans)


(n, m) = [int(x) for x in input().split()]
L = [[int(x) for x in input().split()] for z in range(m)]
maxh = max([x[1] for x in L])

def possible(a, b):
	if abs(a[1] - b[1]) > abs(a[0] - b[0]):
		return False
	return True

def maxp(a, b):
	t = abs(a[0] - b[0])
	t -= abs(a[1] - b[1])
	m = max(a[1], b[1])
	return m + t // 2
poss = True
for i in range(len(L) - 1):
	if not possible(L[i], L[i + 1]):
		poss = False
		break
	maxh = max(maxh, maxp(L[i], L[i + 1]))
maxh = max(maxh, L[0][0] - 1 + L[0][1], n - L[-1][0] + L[-1][1])
if poss:
	print(maxh)
else:
	print('IMPOSSIBLE')


R = lambda : map(int, input().split())
(n, m) = R()
ls = [tuple(R()) for _ in range(m)]
res = max(ls[0][1] + ls[0][0] - 1, ls[-1][-1] + n - ls[-1][0])
for i in range(1, m):
	(d, h) = (ls[i][0] - ls[i - 1][0], abs(ls[i][1] - ls[i - 1][1]))
	if d < h:
		print('IMPOSSIBLE')
		exit()
	else:
		res = max(res, (d - h) // 2 + max(ls[i][1], ls[i - 1][1]))
print(res)


(n, m) = map(int, input().split(' '))
diary = list()
for i in range(m):
	diary.append(list(map(int, input().split(' '))))
actual_distance = [abs(diary[i + 1][1] - diary[i][1]) for i in range(len(diary) - 1)]
max_distance = [diary[i + 1][0] - diary[i][0] for i in range(len(diary) - 1)]
difference = [i[1] - i[0] for i in zip(actual_distance, max_distance)]
max_unknown_hight_left = [diary[0][1] + diary[0][0] - 1]
max_unknown_hight_right = [diary[-1][1] + (n - diary[-1][0])]
if difference != []:
	if min(difference) < 0:
		print('IMPOSSIBLE')
	else:
		max_unknown_hights_between = [diary[i][1] + max_distance[i] // 2 + (diary[i + 1][1] - diary[i][1]) // 2 for i in range(len(diary) - 1)]
		all_hights = [diary[i][1] for i in range(len(diary))] + max_unknown_hights_between + max_unknown_hight_left + max_unknown_hight_right
		print(max(all_hights))
else:
	all_hights = [diary[i][1] for i in range(len(diary))] + max_unknown_hight_left + max_unknown_hight_right
	print(max(all_hights))


(n, m) = map(int, input().split())
h = [None] * m

def calc(h, num):
	r = -1
	for i in range(len(h) - 1):
		n = h[i + 1][0] - h[i][0]
		hd = h[i + 1][1] - h[i][1]
		s = (n + hd) % 2
		if n + hd < s or n - hd < s:
			return 'IMPOSSIBLE'
		u = (hd + n - s) // 2
		r = max(r, h[i][1] + u)
	l = len(h) - 1
	ld = h[l][0]
	lh = h[l][1]
	r = max(r, lh + num - ld)
	r = max(r, h[0][1] + h[0][0] - 1)
	return r
for i in range(m):
	(d, v) = map(int, input().split())
	h[i] = (d, v)
print(calc(h, n))


import math
(n, m) = map(int, input().split())
mass = []
for i in range(m):
	(d, h) = map(int, input().split())
	mass.append((d, h))
max_h = mass[0][1]
flag = True
for j in range(m - 1):
	if abs(mass[j + 1][1] - mass[j][1]) > mass[j + 1][0] - mass[j][0]:
		flag = False
		break
	elif abs(mass[j + 1][1] - mass[j][1]) == mass[j + 1][0] - mass[j][0]:
		if max(mass[j + 1][1], mass[j][1]) > max_h:
			max_h = max(mass[j + 1][1], mass[j][1])
	elif max(mass[j + 1][1], mass[j][1]) + math.floor((mass[j + 1][0] - mass[j][0] - abs(mass[j + 1][1] - mass[j][1])) // 2) > max_h:
		max_h = max(mass[j + 1][1], mass[j][1]) + math.floor((mass[j + 1][0] - mass[j][0] - abs(mass[j + 1][1] - mass[j][1])) // 2)
if mass[len(mass) - 1][0] != n:
	if n - mass[len(mass) - 1][0] + mass[len(mass) - 1][1] > max_h:
		max_h = n - mass[len(mass) - 1][0] + mass[len(mass) - 1][1]
if mass[0][0] != 1:
	if mass[0][0] - 1 + mass[0][1] > max_h:
		max_h = mass[0][0] - 1 + mass[0][1]
if flag:
	print(max_h)
else:
	print('IMPOSSIBLE')


(n, m) = map(int, input().split(' '))
l = [list(map(int, input().split(' '))) for _ in range(m)]
ans = max(l[0][0] + l[0][1] - 1, n - l[-1][0] + l[-1][1])
for i in range(1, m):
	(dd, dh) = (abs(l[i][0] - l[i - 1][0]), abs(l[i][1] - l[i - 1][1]))
	if dd < dh:
		print('IMPOSSIBLE')
		exit()
	ans = max(ans, max(l[i][1], l[i - 1][1]) + (dd - dh >> 1))
print(ans)


def f(d1, h1, d2, h2):
	(lo, hi) = (max(0, h1 - (d2 - d1)), min(10 ** 8, h1 + (d2 - d1)))
	if h2 < lo or h2 > hi:
		return (False, float('-inf'))
	else:
		if h1 < h2:
			(h1, d1) = (h2, d1 + (h2 - h1))
		elif h1 > h2:
			(h2, d2) = (h1, d2 - (h1 - h2))
		return (True, h1 + (d2 - d1) // 2)

def solve(a, n, m):
	ans = float('-inf')
	for i in range(m - 1):
		(possible, maxheight) = f(a[i][0], a[i][1], a[i + 1][0], a[i + 1][1])
		if not possible:
			return float('-inf')
		else:
			ans = max(ans, maxheight)
	return max(ans, a[0][1] + a[0][0] - 1, a[-1][1] + n - a[-1][0])
(n, m) = map(int, input().split())
a = []
for i in range(m):
	(d, h) = map(int, input().split())
	a.append((d, h))
ans = solve(a, n, m)
if ans == float('-inf'):
	print('IMPOSSIBLE')
else:
	print(ans)


def possible(d1, h1, d2, h2):
	if d2 - d1 < abs(h2 - h1):
		return -1
	elif h1 == h2:
		return (d2 - d1) // 2 + h1
	elif h1 > h2:
		diff = h1 - h2
		newd2 = d2 - diff
		if newd2 < d1:
			return -1
		else:
			return (newd2 - d1) // 2 + h1
	else:
		diff = h2 - h1
		newd1 = d1 + diff
		if newd1 > d2:
			return -1
		else:
			return (d2 - newd1) // 2 + h2
info = input().split()
n = int(info[0])
m = int(info[1])
first = input().split()
oldd = int(first[0])
oldh = int(first[1])
answer = oldd - 1 + oldh
bad = False
for i in range(m - 1):
	inf = input().split()
	newd = int(inf[0])
	newh = int(inf[1])
	pos = possible(oldd, oldh, newd, newh)
	if pos == -1:
		print('IMPOSSIBLE')
		bad = True
		break
	elif pos > answer:
		answer = pos
	oldd = newd
	oldh = newh
if not bad:
	endheight = n - oldd + oldh
	if endheight > answer:
		answer = endheight
	print(answer)


import math
(n, m) = map(int, input().split())
a = []
for i in range(m):
	(d, h) = map(int, input().split())
	a.append([d, h])
max_ = -1
c1 = 0
g = a[0][0] - 1 + a[0][1]
if g > max_:
	max_ = g
for i in range(len(a) - 1):
	g = math.floor((a[i + 1][0] - a[i][0] + a[i][1] + a[i + 1][1]) / 2)
	if a[i][1] > g or a[i + 1][1] > g:
		c1 = -1
		break
	elif g > max_:
		max_ = g
g = n - a[len(a) - 1][0] + a[len(a) - 1][1]
if g > max_:
	max_ = g
if c1 != -1:
	print(max_)
else:
	print('IMPOSSIBLE')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
d = [0] * m
h = [0] * m
for i in range(m):
	(d[i], h[i]) = map(int, input().split())
ans = max(d[0] - 1 + h[0], max(h))
for i in range(1, m):
	dd = d[i] - d[i - 1]
	hh = h[i] - h[i - 1]
	if abs(dd) < abs(hh):
		print('IMPOSSIBLE')
		exit()
	max_h = max(h[i], h[i - 1]) + (dd - abs(hh)) // 2
	ans = max(ans, max_h)
ans = max(ans, n - d[-1] + h[-1])
print(ans)


def main():
	import sys
	tokens = [int(i) for i in sys.stdin.read().split()]
	tokens.reverse()
	result = 0
	(n, m) = (tokens.pop(), tokens.pop())
	(pd, ph) = (0, 0)
	for i in range(m):
		(d, h) = (tokens.pop(), tokens.pop())
		if i == 0:
			result = h + (d - 1)
		else:
			delta_d = d - pd
			delta_h = abs(h - ph)
			if delta_h > delta_d:
				print('IMPOSSIBLE')
				return
			else:
				result = max(result, max(h, ph) + (delta_d - delta_h) // 2)
		if i == m - 1:
			result = max(result, h + (n - d))
		(pd, ph) = (d, h)
	print(result)
main()


[n, k] = [int(x) for x in input().split()]
Data = type('Data', (object,), {'index': 0, 'value': 0})
data = [Data() for _ in range(k)]
for i in range(k):
	[data[i].index, data[i].value] = [int(x) for x in input().split()]
data.sort(key=lambda x: x.index)
ans = max(data[0].value + data[0].index - 1, data[k - 1].value + n - data[k - 1].index)
for i in range(1, k):
	L = data[i].index - data[i - 1].index
	minH = min(data[i].value, data[i - 1].value)
	maxV = max(data[i].value, data[i - 1].value)
	if minH + L < maxV:
		ans = -1
		break
	ans = max(ans, (L + minH + maxV) // 2)
if ans < 0:
	print('IMPOSSIBLE')
else:
	print(ans)