You have a long fence which consists of $n$ sections. Unfortunately, it is not painted, so you decided to hire $q$ painters to paint it. $i$-th painter will paint all sections $x$ such that $l_i \le x \le r_i$.

Unfortunately, you are on a tight budget, so you may hire only $q - 2$ painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose $q - 2$ painters optimally. A section is considered painted if at least one painter paints it.


-----Input-----

The first line contains two integers $n$ and $q$ ($3 \le n, q \le 5000$) — the number of sections and the number of painters availible for hire, respectively.

Then $q$ lines follow, each describing one of the painters: $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).


-----Output-----

Print one integer — maximum number of painted sections if you hire $q - 2$ painters.


-----Examples-----
Input
7 5
1 4
4 5
5 6
6 7
3 5

Output
7

Input
4 3
1 1
2 2
3 4

Output
2

Input
4 4
1 1
2 2
2 3
3 4

Output
3

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

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

def lm():
	return list(map(int, input().split()))


n, q=mi()

ints=[]


for _ in range(q):
	st, end=mi()
	ints.append((st,end))


coverage=[10]+[0]*n

for st, end in ints:
	for i in range(st,end+1):
		coverage[i]+=1

total=-1

for val in coverage:
	if not val==0:
		total+=1

singlecount=0
doublecount=0

singles=[0]*(n+1)
#print(total)
doubles=[0]*(n+1)
for i in range(len(coverage)):
	#print(i,singles)
	if coverage[i]==1:
		singlecount+=1
	if coverage[i]==2:
		doublecount+=1
	singles[i]=singlecount
	doubles[i]=doublecount
maxtotal=0
for i in range(len(ints)):
	for j in range(i+1, len(ints)):
		st1=min(ints[i][0],ints[j][0])
		end1=min(ints[i][1],ints[j][1])
		st2, end2=max(ints[i][0],ints[j][0]), max(ints[i][1],ints[j][1])
		#assume st1<=st2
		if end1<st2:
			curtotal=total-(singles[end1]-singles[st1-1])-(singles[end2]-singles[st2-1])
		elif end1<end2:
			curtotal=total-(singles[st2-1]-singles[st1-1])-(doubles[end1]-doubles[st2-1])-(singles[end2]-singles[end1])
		else:
			curtotal=total-(singles[st2-1]-singles[st1-1])-(doubles[end2]-doubles[st2-1])-(singles[end1]-singles[end2])
		maxtotal=max(maxtotal,curtotal)

print(maxtotal)
		









import collections

n , q  = list(map(int , input().split()))
sections = [0]*n
p = []
for _ in range(q):
    l , r = list(map(int , input().split()))
    p.append((l,r))
    for j in range(l,r+1):
        sections[j-1]+=1

aux = n-collections.Counter(sections)[0]
number1 = [0]*n
number2 = [0]*n

for i in range(n):
    if(sections[i]==1):
        for j in range(i,n):
            number1[j]+=1
    elif(sections[i]==2):
        for j in range(i,n):
            number2[j]+=1

ans = -float('inf')
for i in range(len(p)):
    for j in range(len(p)):
        if(j>i):
            a, b = p[i]
            c, d = p[j]
            if(a>c):
                a , c = c , a
                b , d = d , b
            aux1 = number1[b-1]-number1[a-1]+1*(sections[a-1]==1)
            aux2 = number1[d-1]-number1[c-1]+1*(sections[c-1]==1)
            aux3 = abs(number2[c-1]-number2[min(b,d)-1])+1*(sections[c-1]==2)
            if(b<c): aux3 = 0
            ans = max(ans , aux-(aux1+aux2+aux3))
print(ans)


DBG = False
n,q = list(map(int,input().split()))
l = []
r = []
c = [0] * (n+2)
for i in range(q):
  ll,rr = list(map(int,input().split()))
  l.append(ll)
  r.append(rr)
  for j in range(ll,(rr+1)):
    c[j] += 1

acc1 = [0] * (n+2)
acc12 = [0] * (n+2)
for j in range(1,n+1):
  acc1[j] = acc1[j-1] + (1 if c[j] == 1 else 0)
  acc12[j] = acc12[j-1] + (1 if (c[j] == 2) else 0)

minred = 99999999
for i in range(q-1):
  for j in range(i+1,q):
    li = l[i]
    lj = l[j]
    ri = r[i]
    rj = r[j]
    #puts "(#{li} #{ri}) - (#{lj} #{rj}) " if DBG
    if li > lj:
      li, lj = lj, li
      ri, rj = rj, ri
    #end  # now li <= lj

    if rj <= ri:   # li  lj  rj  ri
      oneal = li
      onear = lj-1
      twol = lj
      twor = rj
      onebl = rj+1
      onebr = ri
    elif lj <= ri:   #  li  lj  ri  rj
      oneal = li
      onear = lj-1
      twol = lj
      twor = ri
      onebl = ri+1
      onebr = rj
    else:   #   li  ri    lj  rj
      oneal = li
      onear = ri
      twol = lj
      twor = lj-1  # null
      onebl = lj
      onebr = rj

    onereda = acc1[onear] - acc1[oneal-1]
    oneredb = acc1[onebr] - acc1[onebl-1]
    twored = acc12[twor] - acc12[twol-1]
    redsum = onereda + oneredb + twored
    #puts " - 1l: #{onereda}, 2:#{twored}, 1r: #{oneredb}" if DBG
    minred = min(minred, redsum)

zcnt = 0
for i in range(1,n+1):
  if c[i] == 0:
      zcnt += 1
print(n-zcnt-minred)


n,q=map(int,input().split())
arr=[]
ff=[0]*(5005)
for i in range(q):
	x,y=map(int,input().split())
	for j in range(x,y+1):
		ff[j]+=1
	arr.append([x,y])
ans=0
for i in range(q):
	tt=0
	for j in range(arr[i][0],arr[i][1]+1):
		ff[j]-=1
	for j in range(5005):
		if ff[j]>0:
			tt+=1
	c=[0]*(n+1)
	for j in range(1,n+1):
		c[j]=c[j-1]
		if ff[j]==1:
			c[j]+=1
	# print(ff[0:n+1])
	for j in range(i+1,q):
		ans=max(ans,tt-c[arr[j][1]]+c[arr[j][0]-1])
	for j in range(arr[i][0],arr[i][1]+1):
		ff[j]+=1
print(ans)

# -*- coding: utf-8 -*-

import sys
from copy import copy

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,Q=MAP()

imos=[0]*(N+2)
Pts=[None]*Q
for i in range(Q):
    l,r=MAP()
    Pts[i]=(l,r)
    imos[l]+=1
    imos[r+1]-=1
for i in range(N+1):
    imos[i+1]+=imos[i]

mx=0
for i in range(Q):
    cp=copy(imos)
    l,r=Pts[i]
    for j in range(l, r+1):
        cp[j]-=1
    sm=0
    cnt1=[0]*(N+2)
    for j in range(1, N+1):
        if cp[j]>0:
            sm+=1
        if cp[j]==1:
            cnt1[j]+=1
        cnt1[j+1]+=cnt1[j]
    for j in range(i+1, Q):
        l2,r2=Pts[j]
        mx=max(mx, sm-(cnt1[r2]-cnt1[l2-1]))

print(mx)


n, q = map(int, input().split())
a = []
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    a.append([l, r])

ct = [0] * (n + 1)
for i in a:
    ct[i[0]] += 1
    ct[i[1] + 1] -= 1

ones, twos = [0] * n, [0] * n
s = 0
for i in range(n):
    if i > 0:
        ct[i] += ct[i - 1]
        ones[i] += ones[i - 1]
        twos[i] += twos[i - 1]
    if ct[i] == 1:
        ones[i] += 1
    elif ct[i] == 2:
        twos[i] += 1
    if ct[i] != 0:
        s += 1

ones.append(0)
twos.append(0)

ans = 0
for i in range(q):
    for j in range(i + 1, q):
        rem = 0;
        rem += ones[a[i][1]] - ones[a[i][0] - 1]
        rem += ones[a[j][1]] - ones[a[j][0] - 1]

        l, r = max(a[i][0], a[j][0]), min(a[i][1], a[j][1])
        if r >= l:
            rem += twos[r] - twos[l - 1]
        
        ans = max(ans, s - rem)

print(ans)

n, q = list(map(int, input().split()))
painters = []
sections = [0] * (n + 1)
for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    painters.append([l, r])
    sections[l] += 1
    sections[r + 1] -= 1

cnt1 = [0] * (n + 1)
cnt2 = [0] * (n + 1)
p = 0
total = 0
for i in range(n):
    p += sections[i]
    if p == 1:
        cnt1[i + 1] = cnt1[i] + 1
    else:
        cnt1[i + 1] = cnt1[i]
    if p == 2:
        cnt2[i + 1] = cnt2[i] + 1
    else:
        cnt2[i + 1] = cnt2[i]
    if p > 0:
        total += 1
ans = 0
for i in range(q - 1):
    for j in range(i + 1, q):
        [l1, r1] = painters[i]
        [l2, r2] = painters[j]
        l = max(l1, l2)
        r = min(r1, r2)
        if l <= r:
            t = total - (cnt2[r + 1] - cnt2[l]) - (cnt1[max(r1, r2) + 1] - cnt1[min(l1, l2)])
            ans = max(ans, t)
        else:
            t = total - (cnt1[r1 + 1] - cnt1[l1]) - (cnt1[r2 + 1] - cnt1[l2])
            ans = max(ans, t)
print(ans)


from operator import itemgetter
n,q=list(map(int,input().split()))
cnt=0
ans=[0]*(n)
arr=[0]*q
for i in range(q):
	arr[i]=list(map(int,input().split()))
	for j in range(arr[i][0]-1,arr[i][1],1):
		ans[j]+=1
		if ans[j]==1:
			cnt+=1
cnt1=[0]*(n+1)
cnt2=[0]*(n+1)
# print("ans",*ans)
for i in range(n):
	cnt1[i+1]=cnt1[i]
	cnt2[i+1]=cnt2[i]
	if ans[i]==1:
		cnt1[i+1]+=1
	if ans[i]==2:
		cnt2[i+1]+=1
# print(cnt2)
mac=0
for i in range(q):
	for j in range(i+1,q,1):
		delete=cnt1[arr[i][1]]-cnt1[arr[i][0]-1]+cnt1[arr[j][1]]-cnt1[arr[j][0]-1]
		if arr[j][0]>arr[i][1] or arr[j][1]<arr[i][0]:
			pass
		elif arr[j][0]<=arr[i][1]:
			# print("****",cnt2[min(arr[i][1],arr[j][1])],cnt2[max(arr[j][0]-1,arr[i][0]-1)])
			delete+=cnt2[min(arr[i][1],arr[j][1])]-cnt2[max(arr[j][0]-1,arr[i][0]-1)]

		# print(i,j,delete)
		if cnt-delete>mac:
			mac=cnt-delete
print(mac)






n,q=list(map(int,input().split()))
sec=[list(map(int,input().split())) for _ in range(q)]
sec=sorted(sec,key=lambda x:(x[0],x[1]))
fence=[0]*(n+1)
for i in sec:
    x,y=i[0],i[1]
    x-=1;y-=1
    fence[x]+=1
    fence[y+1]-=1
for i in range(1,n+1):
    fence[i]+=fence[i-1]
zeroes=[0]*(n);ones=[0]*(n);twos=[0]*(n)
zeroes[0]=1 if fence[0]==0 else 0
ones[0]=1 if fence[0]==1 else 0
twos[0]=1 if fence[0]==2 else 0
for i in range(1,n):
    if fence[i]==0:
        zeroes[i]+=zeroes[i-1]+1
    else:
        zeroes[i]=zeroes[i-1]

for i in range(1,n):
    if fence[i]==1:
        ones[i]+=ones[i-1]+1
    else:
        ones[i]=ones[i-1]

for i in range(1,n):
    if fence[i]==2:
        twos[i]+=twos[i-1]+1
    else:
        twos[i]=twos[i-1]
np=0
for i in range(q):
    x1,y1=sec[i][0],sec[i][1]
    x1-=1;y1-=1
    co1=co2=ct=0
    for j in range(i+1,q):
        x2,y2=sec[j][0],sec[j][1]
        x2-=1;y2-=1
        co1=ones[y1]-(0 if x1==0 else ones[x1-1])
        co2=ones[y2]-(0 if x2==0 else ones[x2-1])
        if x2<=y1:
            ct=twos[min(y1,y2)]-(0 if x2==0 else twos[x2-1])
        else:
            ct=0
        np=max(np,n-(co1+co2+ct+zeroes[-1]))
        #print(i,j,np,co1,co2,ct,zeroes[-1],x2,y1)
print(np)
    
        
    


n,q=list(map(int,input().split()))
sec=[list(map(int,input().split())) for _ in range(q)]
sec=sorted(sec,key=lambda x:(x[0],x[1]))
fence=[0]*(n+1)
for i in sec:
    x,y=i[0],i[1]
    x-=1;y-=1
    fence[x]+=1
    fence[y+1]-=1
for i in range(1,n+1):
    fence[i]+=fence[i-1]
zeroes=[0]*(n);ones=[0]*(n);twos=[0]*(n)
zeroes[0]=1 if fence[0]==0 else 0
ones[0]=1 if fence[0]==1 else 0
twos[0]=1 if fence[0]==2 else 0
for i in range(1,n):
    if fence[i]==0:
        zeroes[i]+=zeroes[i-1]+1
    else:
        zeroes[i]=zeroes[i-1]

for i in range(1,n):
    if fence[i]==1:
        ones[i]+=ones[i-1]+1
    else:
        ones[i]=ones[i-1]

for i in range(1,n):
    if fence[i]==2:
        twos[i]+=twos[i-1]+1
    else:
        twos[i]=twos[i-1]
np=0
for i in range(q):
    x1,y1=sec[i][0],sec[i][1]
    x1-=1;y1-=1
    co1=co2=ct=0
    for j in range(i+1,q):
        x2,y2=sec[j][0],sec[j][1]
        x2-=1;y2-=1
        co1=ones[y1]-(0 if x1==0 else ones[x1-1])
        co2=ones[y2]-(0 if x2==0 else ones[x2-1])
        if x2<=y1:
            ct=twos[min(y1,y2)]-(0 if x2==0 else twos[x2-1])
        else:
            ct=0
        np=max(np,n-(co1+co2+ct+zeroes[-1]))
        #print(i,j,np,co1,co2,ct,zeroes[-1],x2,y1)
print(np)


n, m = list(map(int, input().split()))
a = [0 for i in range(n)]
b = [list(map(int, input().split())) for i in range(m)] 
f = [0 for i in range(m)]
g = [[0 for i in range(m)] for j in range(m)]
ans = s = p = q = 0
c = n
for i in range(m):
	for j in range(b[i][0] - 1, b[i][1]):
		a[j] += 1
for i in range(n):
	s += a[i] != 0
	if a[i] == 1:
		for j in range(m):
			if b[j][0] - 1 <= i < b[j][1]:
				f[j] += 1
	if a[i] == 2:
		p = q = -1
		for j in range(m):
			if b[j][0] - 1 <= i < b[j][1]:
				if p == -1:
					p = j
				else:
					q = j
		g[p][q] += 1
for i in range(m):
	for j in range(i + 1, m):
		c = min(c, g[i][j] + f[i] + f[j])
print(s - c)


n,q = map(int, input().strip().split())
count = [0 for i in range(n+1)]
tot = 0
painters = []
for i in range(q):
    l,r = map(int, input().strip().split())
    painters.append([l,r])
    for j in range(l,r+1):
        if count[j] == 0:
            tot += 1
        count[j] += 1
ones = [0 for i in range(n+1)]
twos = [0 for i in range(n+1)]
painters.sort()
for i in range(1,n+1):
    ones[i] = ones[i-1]
    twos[i] = twos[i-1]
    if count[i] == 1:
        ones[i] += 1
    elif count[i] == 2:
        twos[i] += 1
mx = 0
for i in range(q):
    for j in range(i+1,q):
      a = ones[painters[i][1]] - ones[painters[i][0]-1]
      b = ones[painters[j][1]] - ones[painters[j][0]-1]
      if painters[j][0] <= painters[i][1]:
          c = twos[min(painters[i][1],painters[j][1])] - twos[painters[j][0]-1]
      else:
          c = 0
      mx = max(mx,tot - a -b -c)
print (mx)

n,q = [int(x) for x in input().split()]

p = []

for _ in range(q):
    p.append([int(x)-1 for x  in input().split()])


def pre(ind):
    res = [0 for _ in range(n)]
    for i in range(q):
        if i == ind : continue
        res[p[i][0]] += 1
        if p[i][1] + 1 < n:
            res[p[i][1] + 1] -= 1
    t = 0
    total = 0
    for i in range(n):
        t += res[i]
        res[i] = t
        if res[i] > 0:
            total += 1
    for i in range(n):
        if res[i] > 1 : res[i] = 0
    for i in range(1,n):
        res[i] += res[i-1]
    return total,res


best = 0

for i in range(q):
    total,table = pre(i)
    for j in range(q):
        if j== i : continue
        count = table[p[j][1]]
        if p[j][0] > 0 :
            count -= table[p[j][0] - 1] 
        best = max(best,total-count)

print(best)


n, q = list(map(int, input().split()))
C = [0 for _ in range(n)]
X = [[-1, -1] for _ in range(n)]
ii = 1
for i in range(q):
    l, r = list(map(int, input().split()))
    ii += 1
    l -= 1
    r -= 1
    for j in range(l, r+1):
        if C[j] <= 2:
            C[j] += 1
            if C[j] <= 2:
                X[j][C[j]-1] = i
s = len([c for c in C if c > 0])

ma = 0
for i in range(q):
    Y = [0] * q
    Y[i] = 10**10
    y = 0
    for j in range(n):
        if C[j] == 2:
            if i == X[j][0] or i == X[j][1]:
                Y[X[j][0]] += 1
                Y[X[j][1]] += 1
        elif C[j] == 1:
            if i == X[j][0]:
                y += 1
            else:
                Y[X[j][0]] += 1
            
    ma = max(ma, s-min(Y)-y)

print(ma)


# -*- coding: utf-8 -*-
# @Time    : 2019/3/7 13:43
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Painting the Fence.py


def main():
    n, q = list(map(int, input().split()))
    painters = []
    for _ in range(q):
        painters.append(list(map(int, input().split())))
    # print(painters)

    ret = 0
    for index in range(q):
        mask = [0] * (n + 1)
        for i in range(q):
            if i == index:
                continue
            left, right = painters[i]
            mask[left - 1] += 1
            mask[right] -= 1

        curr_sum, paint_count = 0, 0
        section_count = [0] * n
        for i in range(n):
            curr_sum += mask[i]
            section_count[i] = curr_sum
            if section_count[i] > 0:
                paint_count += 1

        one_count = [0] * (n + 1)
        for i in range(n):
            one_count[i + 1] = one_count[i] + (1 if section_count[i] == 1 else 0)

        desc_ones = n
        for i in range(q):
            if i == index:
                continue
            left, right = painters[i]
            desc_ones = min(desc_ones, one_count[right] - one_count[left - 1])

        ret = max(ret, paint_count - desc_ones)
    print(ret)


def __starting_point():
    main()

__starting_point()



def get_intersection(l1, r1, l2, r2):
    if min(r1, r2) < max(l1, l2):
        return -1, -1
    else:
        return max(l1, l2), min(r1, r2)

def cumsum(ones, l, r):
    ans = ones[r]
    if l != 1:
        ans -= ones[l-1]

    return ans

def main():

    n,q = [int(x) for x in input().split(' ')]
    cnts = [0 for i in range(n+1)]
    pep = []

    for i in range(q):
        l,r = [int(x) for x in input().split(' ')]
        pep.append((l,r))
        cnts[l] += 1
        if r != n:
            cnts[r+1] -= 1

    ones = [0 for i in range(n+1)]
    twos = [0 for i in range(n+1)]
    tot = 0

    for i in range(1, n+1):
        cnts[i] += cnts[i-1]
        tot += cnts[i] != 0

        if cnts[i] == 1:
            ones[i] += 1
        elif cnts[i] == 2:
            twos[i] += 1

        ones[i] += ones[i-1]
        twos[i] += twos[i-1]

    best = -1
    for i in range(len(pep)):
        for j in range(i+1, len(pep)):
            cur_ans = tot - cumsum(ones, *pep[i])
            cur_ans -= cumsum(ones, *pep[j])

            l, r = get_intersection(*pep[i], *pep[j])

            if l != -1:
                cur_ans -= cumsum(twos, l, r)

            best = max(best, cur_ans)

    print(best)


def __starting_point():
    main()

__starting_point()

def main():
    n, q = map(int, input().split())
    cnt = [0] * (n+1)
    ll = [0] * q
    rr = [0] * q

    for i in range(q):
        l, r = map(int, input().split())
        cnt[l] += 1
        if r < n:
            cnt[r+1] -= 1
        ll[i] = l
        rr[i] = r

    for i in range(1, n+1):
        cnt[i] += cnt[i-1]

    pref1 = [0] * (n+1)
    pref2 = [0] * (n+1)
    for i in range(1, n+1):
        if cnt[i] == 1:
            pref1[i] = 1
        pref1[i] += pref1[i-1]

        if cnt[i] == 2:
            pref2[i] = 1
        pref2[i] += pref2[i-1]

    all = 0
    for i in range(1, n+1):
        if cnt[i] > 0:
            all += 1


    def getIntersection(l1, r1, l2, r2):
        start = max(l1, l2)
        end = min(r1, r2)
        if start <= end:
            return start, end
        return None


    maxBlocks = 0
    for i in range(q):
        for j in range(i+1, q):
            all_ij = all
            inter = getIntersection(ll[i], rr[i], ll[j], rr[j])
            if inter:
                interL, interR = inter
                all_ij -= (pref1[interL-1] - pref1[min(ll[i], ll[j])-1])
                all_ij -= (pref1[max(rr[i], rr[j])] - pref1[interR])
                all_ij -= (pref2[interR] - pref2[interL-1])
            else:
                all_ij -= (pref1[rr[i]] - pref1[ll[i]-1])
                all_ij -= (pref1[rr[j]] - pref1[ll[j]-1])

            maxBlocks = max(maxBlocks, all_ij)

    print(maxBlocks)


def __starting_point():
    main()
__starting_point()

import sys
import copy
input = sys.stdin.readline

n,q=list(map(int,input().split()))
Q=[list(map(int,input().split())) for i in range(q)]
Q.sort()

LIST=[0]*(n+2)
for l ,r in Q:
    LIST[l]+=1
    LIST[r+1]-=1

SUM=[0]
for i in range(1,n+2):
    SUM.append(LIST[i]+SUM[-1])

ONES=[0]
TWOS=[0]

for i in range(1,n+2):
    if SUM[i]==1:
        ONES.append(ONES[-1]+1)
    else:
        ONES.append(ONES[-1])

    if SUM[i]==2:
        TWOS.append(TWOS[-1]+1)
    else:
        TWOS.append(TWOS[-1])

ANS=sum([1 for a in SUM if a>=1])
MINUS=10**10
for i in range(q-1):
    for j in range(i+1,q):
        l0,r0=Q[i][0],Q[i][1]
        l1,r1=Q[j][0],Q[j][1]

        if l1>r0:
            MICAN=(ONES[r0]-ONES[l0-1])+(ONES[r1]-ONES[l1-1])

        elif l1<=r0 and r1>r0:
            MICAN=(ONES[l1-1]-ONES[l0-1])+(TWOS[r0]-TWOS[l1-1])+(ONES[r1]-ONES[r0])

        elif l1<=r0 and r1<=r0:
            MICAN=(ONES[l1-1]-ONES[l0-1])+(TWOS[r1]-TWOS[l1-1])+(ONES[r0]-ONES[r1])

        if MICAN<MINUS:
            MINUS=MICAN
            
        #print(i,j)
        #print(l0,r0,l1,r1)
        #print(MICAN)

print(ANS-MINUS)
                                                    
                                                                                 
        







def __starting_point():
    N,Q = list(map(int,input().strip().split()))
    
    painters = []
    for i in range(Q):
        painters.append(tuple(map(int,input().strip().split())))
    C = [[] for i in range(N+1)]
    for i in range(len(painters)):
        start,end = painters[i]
        for j in range(start,end+1):
            C[j].append(i)
    C = C[1:]
    total = sum(1 for i in C if len(i) > 0)
    count = [[0 for i in range(Q)] for j in range(Q)]
    for i in range(N):
        if len(C[i]) == 2:
            count[C[i][0]][C[i][1]] += 1
            count[C[i][1]][C[i][0]] += 1
        if len(C[i]) == 1:
            for j in range(Q):
                if j != C[i][0]:
                    count[C[i][0]][j] += 1
                    count[j][C[i][0]] += 1
    mini = 100000
    for i in range(Q):
        for j in range(Q):
            if i != j and count[i][j] < mini:
                mini = count[i][j]
    print(total - mini)
    

__starting_point()

n, q = list(map(int, input().split()))
a = []
ar = [0 for i in range(n + 1)]
for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    a.append((l, r))
    ar[l] += 1
    ar[r + 1] += -1
plus = 0
for i in range(n):
    plus += ar[i]
    ar[i] = plus

ans = 0

for i in range(q):
    for j in range(a[i][0], a[i][1] + 1):
        ar[j] -= 1

    pref = [0]
    count = 0
    for pos in range(n):
        if ar[pos] > 0:
            count += 1

        value = 0
        if ar[pos] == 1:
            value = 1
        pref.append(value + pref[-1])

    for pos in range(q):
        if pos != i:
            ans = max(ans, count - (pref[a[pos][1] + 1] - pref[a[pos][0]]))

    for j in range(a[i][0], a[i][1] + 1):
        ar[j] += 1

print(ans)


cnt = lambda s, x: s.count(x)
ii = lambda: int(input())
si = lambda: input()
f = lambda: list(map(int, input().split()))
dgl = lambda: list(map(int, input()))
il = lambda: list(map(int, input().split()))
n,k=f()
l=[0]*(n+10)
p=[]
mx=0
for _ in range(k):
    a,b=f()
    p.append([a,b])
    l[a]+=1
    l[b+1]-=1

psf=[l[0]]

for _ in range(1,n+2):
    psf.append(psf[-1]+l[_])

w=sum(i>0 for i in psf)

psf1,psf2=[0],[0]
for i in range(1,n+2):
    if psf[i]==1:
        psf1.append(psf1[-1]+1)
    else:
        psf1.append(psf1[-1])
    if psf[i]==2:
        psf2.append(psf2[-1]+1)
    else:
        psf2.append(psf2[-1])


for i in range(k-1):
    for j in range(i+1,k):
        x=w-(psf1[p[i][1]]-psf1[p[i][0]-1])-(psf1[p[j][1]]-psf1[p[j][0]-1])
        l,r=max(p[i][0],p[j][0]),min(p[i][1],p[j][1])
        if l<=r:
            x+=psf1[r]-psf1[l-1]
            x-=psf2[r]-psf2[l-1]
        mx=max(x,mx)


print(mx)


import sys
# sys.stdin = open('input.txt')
n, q = list(map(int, input().split()))
scanline = [0] * n
mal = []
ans = 0
for i in range(q):
    a, b = list(map(int, input().split()))
    a -= 1
    mal.append((a, b))
    scanline[a] += 1
    if b < n:
        scanline[b] -= 1

for i in range(q):
    scanline[mal[i][0]] -= 1
    if mal[i][1] < n:
        scanline[mal[i][1]] += 1
    ots = [0] * (n + 1)
    not0 = 0
    cur = 0
    inans = -10000000000
    # print(scanline)
    for j in range(1, n + 1):
        cur += scanline[j - 1]
        if cur != 0:
            not0 += 1
        if cur == 1:
            ots[j] = ots[j - 1] + 1
        else:
            ots[j] = ots[j - 1]
    # print(ots)
    for j in range(q):
        if j == i:
            continue
        inans = max(inans, ots[mal[j][0]] - ots[mal[j][1]])
    # print(inans)
    ans = max(ans, inans + not0)
    scanline[mal[i][0]] += 1
    if mal[i][1] < n:
        scanline[mal[i][1]] -= 1
print(ans)


n,q=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(q)]
c=[0]*5005
for i in range(q):
    for j in range(a[i][0],a[i][1]+1):
        c[j]+=1
ans=0
for i in range(q):
    tmp=0
    d=c[:]
    for j in range(a[i][0],a[i][1]+1):
        d[j]-=1
    for j in range(5005):
        if d[j]>0:tmp+=1
    b=[0]*5005
    for j in range(1,n+1):
        b[j]=b[j-1]
        if d[j]==1:b[j]+=1
    for j in range(i+1,q):
        ans=max(ans,tmp-b[a[j][1]]+b[a[j][0]-1])
print(ans)