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: interview

Starter code:

Solutions:
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) # "free" days for going up-down
        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 = list(map(int,input().split(' ')))
d = []
for i in range(m):
    d.append(list(map(int,input().split(' '))))
ispossible = True
maxheights = []
# first and last days
maxheights.append(d[0][1]+d[0][0]-1)
maxheights.append(d[-1][1]+n-d[-1][0])
# other days
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')


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
   else: 
       if 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')

n, m = list(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)))
    return

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


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)


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

import sys


n, m = list(map(int, str.split(sys.stdin.readline())))
pd = ph = None
top = None
for _ in range(m):

    d, h = list(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")
            return

        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)


n, m = list(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')
        return
    ans = max(ans, max(l[i][1], l[i - 1][1]) + ((dd - dh) >> 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, 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")

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]
    else:
        if 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])
        else:
            if 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)

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 = input().split()
n = int(n)
m = int(m)
#print(str(n)+' '+str(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")
        return
    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 = list(map(int,input().split()))
H = []
for i in range(M):
    d,h = list(map(int,input().split()))
    H.append((d,h))
#print(H[0])
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)

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


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


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



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.readMockInput()
s.solve()

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

		#crap - fix this
		if(i == m-1) :
			max_height = max(max_height, n-d+h)

		continue

#	print("calculating  ",  prev_d, prev_h,d,h) 
	intersection = (-1*(prev_d - prev_h) + (d + h))/2
	day = (intersection - prev_h) + prev_d
#	print("intersection: ", intersection, " at day ", day)

	if(day > d or day < prev_d) :
#	if(day > 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")

#16160178


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
    else:
        if (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')

#  Precondition: d1 < d2
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:  # h1 < h2
        diff = h2 - h1
        newd1 = d1+diff
        if newd1 > d2:
            return -1
        else:
            return (d2-newd1)//2 + h2

# print ("Input n and m (days and notes)")
info = input().split()
n = int(info[0])
m = int(info[1])

# print ("Input first day/height pair")
first = input().split()
oldd = int(first[0])
oldh = int(first[1])
answer = (oldd-1) + oldh  # Compute what day one could be

bad = False
for i in range(m-1):
    # print ("Input next day/height pair")
    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
    else:   #  Can do it--check to see if a greater height
        if pos > answer:
            answer = pos
    oldd = newd
    oldh = newh

#  If we are still OK, compute what the last day could be
if (not bad):
    endheight = (n - oldd) + oldh
    if endheight > answer:
        answer = endheight
    print (answer)
        
        
    
    


        
       


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 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')
		return
	dd -= dh
	res = max(res, max(ph, h) + dd // 2)
	pd = d
	ph = h
res = max(res, ph + (n - pd))
print(res)