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: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
(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)


(n, q) = 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)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
ar = []
for i in range(q):
	ar.append(list(map(int, input().split())))
li = [0] * (n + 1)
for i in range(q):
	for j in range(ar[i][0], ar[i][1] + 1):
		li[j] += 1
dic = {}
matrix = []
for i in range(q + 1):
	tem = []
	for j in range(q + 1):
		tem.append(0)
	matrix.append(tem.copy())
for i in range(1, n + 1):
	mem = []
	if li[i] == 1:
		for j in range(q):
			if ar[j][0] <= i and ar[j][1] >= i:
				mem.append(j)
				break
	elif li[i] == 2:
		for j in range(q):
			if ar[j][0] <= i and ar[j][1] >= i:
				mem.append(j)
				break
		for j in range(q):
			if ar[j][0] <= i and ar[j][1] >= i and (mem[0] != j):
				mem.append(j)
				break
	if li[i] == 1:
		matrix[mem[0]][0] += 1
	elif li[i] == 2:
		matrix[mem[0]][mem[1]] += 1
su = 0
for i in range(1, n + 1):
	if li[i] != 0:
		su += 1
ans = 0
for i in range(q):
	for j in range(i + 1, q):
		s1 = matrix[i][0]
		s2 = matrix[j][0]
		s3 = matrix[i][j]
		ans = max(ans, su - s1 - s2 - s3)
print(ans)


(N, Q) = 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)


DBG = False
(n, q) = map(int, input().split())
l = []
r = []
c = [0] * (n + 2)
for i in range(q):
	(ll, rr) = 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]
		if li > lj:
			(li, lj) = (lj, li)
			(ri, rj) = (rj, ri)
		if rj <= ri:
			oneal = li
			onear = lj - 1
			twol = lj
			twor = rj
			onebl = rj + 1
			onebr = ri
		elif lj <= ri:
			oneal = li
			onear = lj - 1
			twol = lj
			twor = ri
			onebl = ri + 1
			onebr = rj
		else:
			oneal = li
			onear = ri
			twol = lj
			twor = lj - 1
			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
		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())
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(np)


import sys
(n, q) = map(int, input().split())
scanline = [0] * n
mal = []
ans = 0
for i in range(q):
	(a, b) = 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
	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]
	for j in range(q):
		if j == i:
			continue
		inans = max(inans, ots[mal[j][0]] - ots[mal[j][1]])
	ans = max(ans, inans + not0)
	scanline[mal[i][0]] += 1
	if mal[i][1] < n:
		scanline[mal[i][1]] -= 1
print(ans)


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


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


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)
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
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]:
			delete += cnt2[min(arr[i][1], arr[j][1])] - cnt2[max(arr[j][0] - 1, arr[i][0] - 1)]
		if cnt - delete > mac:
			mac = cnt - delete
print(mac)


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)


from itertools import accumulate
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
p = [list(map(int, input().split())) for i in range(m)]
ans = 0
imos = [0] * (n + 2)
for i in range(m):
	(l, r) = p[i]
	imos[l] += 1
	imos[r + 1] -= 1
acc = list(accumulate(imos))
for i in range(m):
	anstmp = n
	accc = acc[:]
	(l, r) = p[i]
	for j in range(l, r + 1):
		accc[j] -= 1
	for j in range(1, n + 1):
		if accc[j] == 1:
			continue
		if accc[j] == 0:
			anstmp -= 1
		accc[j] = 0
	aacc = list(accumulate(accc))
	for j in range(i + 1, m):
		(l, r) = p[j]
		ans = max(ans, anstmp - aacc[r] + aacc[l - 1])
print(ans)


import sys
import copy
input = sys.stdin.readline
(n, q) = 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(ANS - MINUS)


(n, q) = map(int, input().split())
I = []
for _ in range(q):
	(a, b) = map(int, input().split())
	I.append([a - 1, b - 1])
c = [0] * n
ans = 0
for (a, b) in I:
	for i in range(a, b + 1):
		c[i] += 1
for (i, (a, b)) in enumerate(I):
	for j in range(a, b + 1):
		c[j] -= 1
	total = sum((int(c[j] > 0) for j in range(n)))
	d = [int(c[j] == 1) for j in range(n)]
	for j in range(1, n):
		d[j] += d[j - 1]
	mn = 1 << 32
	for j in range(q):
		if i == j:
			continue
		(l, r) = I[j]
		mn = min(d[r] - (d[l - 1] if l >= 1 else 0), mn)
	ans = max(ans, total - mn)
	for j in range(a, b + 1):
		c[j] += 1
print(ans)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
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')

class SegmentTree1:

	def __init__(self, data, default=9999999, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def intersect(intervals):
	l = intervals[0][0]
	r = intervals[0][1]
	for i in range(1, 2):
		if intervals[i][0] > r or intervals[i][1] < l:
			return (-1, -1)
		else:
			l = max(l, intervals[i][0])
			r = min(r, intervals[i][1])
	return (l, r)
(n, q) = map(int, input().split())
a = [0] * n
b = [0] * n
tot = [0] * (n + 1)
a1 = [0] * q
b1 = [0] * q
for i in range(q):
	(a1[i], b1[i]) = map(int, input().split())
	tot[a1[i] - 1] += 1
	tot[b1[i]] -= 1
for i in range(1, n + 1):
	tot[i] += tot[i - 1]
ans = n
for i in range(n):
	if tot[i] == 1:
		a[i] = 1
	elif tot[i] == 2:
		b[i] = 1
	elif tot[i] == 0:
		ans -= 1
tr = 0
w = [0] * n
w1 = [0] * n
w[0] = a[0]
for i in range(1, n):
	w[i] = a[i] + w[i - 1]
w = [0] + w
w1[0] = b[0]
for i in range(1, n):
	w1[i] = b[i] + w1[i - 1]
w1 = [0] + w1
for i in range(q):
	for j in range(i + 1, q):
		(l, r) = intersect([[a1[i], b1[i]], [a1[j], b1[j]]])
		if l == -1 and r == -1:
			e = ans - (w[b1[i]] - w[a1[i] - 1]) - (w[b1[j]] - w[a1[j] - 1])
			tr = max(e, tr)
		else:
			a2 = min(a1[i], a1[j])
			b2 = max(b1[i], b1[j])
			e = ans - (w[l - 1] - w[a2 - 1]) - (w[b2] - w[r]) - (w1[r] - w1[l - 1])
			tr = max(tr, e)
print(tr)


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


import itertools

def paintTheFence(ranges, n, q):
	ans = 0
	for i in range(q):
		painters_count = [0] * (n + 1)
		for j in range(q):
			if j == i:
				continue
			(l, r) = (ranges[j][0] - 1, ranges[j][1] - 1)
			painters_count[l] += 1
			painters_count[r + 1] -= 1
		total_painted = 0
		painted_fence_length = [0]
		sum1 = 0
		sum2 = 0
		for j in range(len(painters_count)):
			sum1 += painters_count[j]
			if sum1 > 0:
				total_painted += 1
			if sum1 == 1:
				sum2 += 1
			painted_fence_length.append(sum2)
		for j in range(q):
			if j == i:
				continue
			(l, r) = (ranges[j][0] - 1, ranges[j][1] - 1)
			painted = painted_fence_length[r + 1] - painted_fence_length[l]
			actual = total_painted - painted
			ans = max(ans, actual)
	return ans
(n, q) = map(int, input().split())
ranges = []
for _ in range(q):
	ranges.append(list(map(int, input().split())))
print(paintTheFence(ranges, n, q))


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
(n, q) = kk()
nr = [0] * (n + 1)
qs = [None] * q
for _ in range(q):
	(l, r) = kk()
	qs[_] = (l, r)
	while l <= r:
		nr[l] += 1
		l += 1
val = n - nr.count(0) + 1
m = 0
for i in range(q):
	(l, r) = qs[i]
	while l <= r:
		nr[l] -= 1
		if nr[l] == 0:
			val -= 1
		l += 1
	if val > m:
		for j in range(i + 1, q):
			(l, r) = qs[j]
			cv = 0
			while l <= r:
				if nr[l] == 1:
					cv += 1
				l += 1
			if m < val - cv:
				m = val - cv
	(l, r) = qs[i]
	while l <= r:
		nr[l] += 1
		if nr[l] == 1:
			val += 1
		l += 1
print(m)


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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:
			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')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def primeNums():
	N = 10 ** 5
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
mx = 5001
lst = [0 for i in range(mx)]
dp = [0 for i in range(mx)]
(n, m) = zzz()
for i in range(1, n + 1):
	lst[i] = i + 1
for i in range(1, m + 1):
	(l, r) = zzz()
	for j in range(l, r + 1):
		lst[j] = min(lst[j], l)
for k in range(1, m - 1):
	for i in range(n, 0, -1):
		lsti = lst[i]
		dp[i] = max(dp[lsti - 1] + i - lsti + 1, dp[i])
	for i in range(1, n + 1):
		dp[i] = max(dp[i], dp[i - 1])
print(dp[n])


maxn = 5001
lst = [0 for _ in range(maxn)]
dp = [0 for _ in range(maxn)]
(n, m) = map(int, input().split())
for i in range(1, n + 1):
	lst[i] = i + 1
for i in range(1, m + 1):
	(l, r) = input().split(' ')
	(l, r) = (int(l), int(r))
	for j in range(l, r + 1):
		lst[j] = min(lst[j], l)
for k in range(1, m - 1):
	for i in range(n, 0, -1):
		lst_i = lst[i]
		dp[i] = max(dp[lst_i - 1] + i - lst_i + 1, dp[i])
	for i in range(1, n + 1):
		dp[i] = max(dp[i], dp[i - 1])
print(dp[n])


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


from sys import stdin, stdout
import math
(N, M) = [int(x) for x in stdin.readline().split()]
paint = [0] * N
data = []
for i in range(M):
	(L, R) = [int(x) for x in stdin.readline().split()]
	for k in range(L - 1, R):
		paint[k] += 1
	data.append([L, R])
res = 0
for i in range(M):
	(L, R) = data[i]
	for k in range(L - 1, R):
		paint[k] -= 1
	p = 0
	prefix = [0] * N
	s = 0
	for j in range(N):
		if paint[j] > 0:
			p += 1
		if paint[j] == 1:
			s += 1
		prefix[j] = s
	for j in range(M):
		if i != j:
			(l, r) = data[j]
			l -= 1
			r -= 1
			if l == 0:
				d = prefix[r]
			else:
				d = prefix[r] - prefix[l - 1]
			res = max(res, p - d)
	for k in range(L - 1, R):
		paint[k] += 1
print(res)


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


import sys
sys.setrecursionlimit(1000000)
(n, q) = map(int, input().split())
md = n
sc = [[] for i in range(n)]
for wi in range(q):
	(l, r) = map(lambda x: int(x) - 1, input().split())
	for i in range(l, r + 1):
		if len(sc[i]) == 3:
			continue
		sc[i].append(wi)
s = [[0 for i in range(q)] for i in range(q)]
for si in sc:
	if len(si) == 0:
		md -= 1
	elif len(si) == 1:
		s[si[0]][si[0]] += 1
	elif len(si) == 2:
		s[si[0]][si[1]] += 1
ml = md
for i in range(q):
	locml = ml
	for j in range(i + 1, q):
		locml = min(locml, s[i][i] + s[i][j] + s[j][j])
	ml = min(ml, locml)
print(md - ml)


(n, k) = map(int, input().split())
c = [0] * (n + 1)
q = []
for i in range(k):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	q.append((x, y))
	c[x] += 1
	c[y + 1] -= 1
for i in range(1, n):
	c[i] += c[i - 1]
ans = 0
for i in range(k):
	for g in range(q[i][0], q[i][1] + 1):
		c[g] -= 1
	on = [0] * n
	color = 0
	for g in range(n):
		if c[g] > 0:
			color += 1
		if c[g] == 1:
			on[g] = 1
	for g in range(1, n):
		on[g] += on[g - 1]
	for j in range(i + 1, k):
		(x, y) = q[j]
		p = 0
		if x == 0:
			p = on[y]
		else:
			p = on[y] - on[x - 1]
		ans = max(ans, color - p)
	for g in range(q[i][0], q[i][1] + 1):
		c[g] += 1
print(ans)


(n, q) = map(int, input().split())
lr = []
painter_cnt = [0] * n
for _ in range(q):
	(l, r) = map(int, input().split())
	lr.append((l - 1, r - 1))
	for i in range(l - 1, r):
		painter_cnt[i] += 1
ans = 0
for i in range(q):
	(li, ri) = lr[i]
	s = 0
	acc = [0]
	for j in range(n):
		c = painter_cnt[j]
		if li <= j <= ri:
			c -= 1
		if c > 0:
			s += 1
		acc.append(acc[-1] + (1 if c == 1 else 0))
	for j in range(q):
		if j == i:
			continue
		(lj, rj) = lr[j]
		ans = max(ans, s - (acc[rj + 1] - acc[lj]))
print(ans)


(n, q) = map(int, input().split())
arr = [[] for i in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	for j in range(l - 1, r):
		arr[j].append(i)
count = [[0 for i in range(q)] for i in range(q)]
total = 0
for i in arr:
	if len(i) != 0:
		total += 1
	if len(i) == 1:
		for j in range(q):
			if j == i[0]:
				continue
			count[i[0]][j] += 1
			count[j][i[0]] += 1
	elif len(i) == 2:
		count[i[0]][i[1]] += 1
		count[i[1]][i[0]] += 1
maxi = -1
for i in range(q):
	for j in range(q):
		if i != j:
			maxi = max(maxi, total - count[i][j])
print(maxi)


(n, q) = map(int, input().split())
f = [0 for i in range(n)]
qm = []
for i in range(q):
	(x, y) = map(int, input().split())
	for j in range(x - 1, y):
		f[j] += 1
	qm.append([x, y])
c1 = [0]
for i in range(n):
	if f[i] == 1:
		c1.append(c1[-1] + 1)
	else:
		c1.append(c1[-1])
c2 = [0]
for i in range(n):
	if f[i] == 2:
		c2.append(c2[-1] + 1)
	else:
		c2.append(c2[-1])
res = 0
for i in range(n):
	if f[i] > 0:
		res += 1
ma = 0
for i in range(q):
	for j in range(i + 1, q):
		(l, r) = qm[i]
		(x, y) = qm[j]
		if l > x:
			(l, r, x, y) = (x, y, l, r)
		if r < x:
			a = c1[r] - c1[l - 1] + c1[y] - c1[x - 1]
		elif y <= r:
			a = c2[y] - c2[x - 1] + c1[r] - c1[l - 1] - (c1[y] - c1[x - 1])
		else:
			a = c1[x - 1] - c1[l - 1] + c2[r] - c2[x - 1] + c1[r] - c1[x - 1] + c1[y] - c1[r]
		ma = max(res - a, ma)
print(ma)


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


def main():
	(n, q) = map(int, input().split())
	painters = []
	for _ in range(q):
		painters.append(list(map(int, input().split())))
	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)
main()


(n, q) = map(int, input().split())
zab = [0] * 5001
a = []
for i in range(q):
	(l, r) = map(int, input().split())
	a.append([l, r])
	for j in range(l, r + 1):
		zab[j] += 1
ans = 0
for i in range(q):
	fl = 0
	d = zab.copy()
	for j in range(a[i][0], a[i][1] + 1):
		d[j] -= 1
	for j in range(5001):
		if d[j] > 0:
			fl += 1
	b = [0] * 5001
	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, fl - b[a[j][1]] + b[a[j][0] - 1])
print(ans)


import sys
input = sys.stdin.buffer.readline
(n, q) = [int(i) for i in input().split()]
n += 1
a = [[] for i in range(n)]
for i in range(q):
	(li, ri) = [int(i) for i in input().split()]
	for j in range(li - 1, ri):
		a[j].append(i)
dp = [[0] * q for i in range(q)]
z = 0
for i in a:
	if len(i) == 0:
		z += 1
	elif len(i) == 1:
		dp[i[0]][i[0]] += 1
	elif len(i) == 2:
		dp[i[0]][i[1]] += 1
		dp[i[1]][i[0]] += 1
m = 10 ** 9
for i in range(q):
	tm = dp[i][i]
	for j in range(i + 1, q):
		tm += dp[i][j]
		tm += dp[j][j]
		m = min(tm, m)
		tm -= dp[i][j]
		tm -= dp[j][j]
print(n - m - z)


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)
doubles = [0] * (n + 1)
for i in range(len(coverage)):
	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]))
		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)


input = __import__('sys').stdin.readline
(n, q) = map(int, input().split())
a = [0] * (n + 1)
inp = []
for _ in range(q):
	(l, r) = map(int, input().split())
	a[l - 1] += 1
	a[r] -= 1
	inp.append([l, r])
azero = 0
for i in range(1, n):
	a[i] += a[i - 1]
	if a[i] == 0:
		azero += 1
ans = 0
for i in range(q):
	(l1, r1) = inp[i]
	b = a.copy()
	c = [0] * (n + 1)
	bzero = 0
	for j in range(n):
		if l1 - 1 <= j < r1:
			b[j] -= 1
		if b[j] == 0:
			bzero += 1
		if b[j] == 1:
			c[j + 1] = c[j] + 1
		else:
			c[j + 1] = c[j]
	for j in range(i + 1, q):
		(lj, rj) = inp[j]
		ans = max(ans, n - bzero - c[rj] + c[lj - 1])
print(ans)


(n, m) = [int(i) for i in input().split()]
arr = []
cnt = [0] * (n + 1)
for i in range(m):
	(a, b) = [int(i) for i in input().split()]
	a -= 1
	b -= 1
	arr.append((a, b))
	cnt[a] += 1
	cnt[b + 1] -= 1
for i in range(1, n):
	cnt[i] += cnt[i - 1]
answer = 0

def getlost(l, r, ones):
	if l == 0:
		return ones[r]
	return ones[r] - ones[l - 1]
for i in range(m):
	coutpos = 0
	ones = [0] * n
	for j in range(arr[i][0], arr[i][1] + 1):
		cnt[j] -= 1
	for j in range(0, n):
		if cnt[j] > 0:
			coutpos += 1
		if cnt[j] == 1:
			ones[j] += 1
	for j in range(1, n):
		ones[j] += ones[j - 1]
	for j in range(i + 1, m):
		get = getlost(arr[j][0], arr[j][1], ones)
		answer = max(answer, coutpos - get)
	for j in range(arr[i][0], arr[i][1] + 1):
		cnt[j] += 1
print(answer)


import sys
from collections import defaultdict

def fill(filled, lim):
	(l, r) = (lim[0], lim[1])
	for i in range(l - 1, r):
		filled[i] += 1
(n, q) = map(int, sys.stdin.readline().split())
paint = [[0, 0] for _ in range(q)]
filled = [0 for _ in range(n)]
for _ in range(q):
	(l, r) = map(int, sys.stdin.readline().split())
	paint[_] = [l, r]
	for i in range(l - 1, r):
		filled[i] += 1
total = 0
for i in range(n):
	total += filled[i] > 0
cur = n
for i in range(q):
	d = [0 for _ in range(n)]
	count1 = 0
	for j in range(paint[i][0] - 1, paint[i][1]):
		filled[j] -= 1
		count1 += filled[j] == 0
	for j in range(n):
		if filled[j] == 1:
			d[j] = 1
	pre = [0 for _ in range(n + 1)]
	for j in range(1, n + 1):
		pre[j] = pre[j - 1] + d[j - 1]
	for j in range(i):
		count2 = pre[paint[j][1]] - pre[paint[j][0] - 1]
		cur = min(cur, count1 + count2)
	for j in range(i + 1, q):
		count2 = pre[paint[j][1]] - pre[paint[j][0] - 1]
		cur = min(cur, count1 + count2)
	fill(filled, paint[i])
ans = total - cur
print(ans)


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


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict
import math
import heapq

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()
(n, q) = listIn()
li = [0] * (n + 1)
li2 = [[] for i in range(n + 1)]
for i in range(q):
	(l, r) = listIn()
	for j in range(l, r + 1):
		li[j] += 1
		li2[j].append(i + 1)
mtx = []
for i in range(q + 1):
	temp = [0] * (q + 1)
	mtx.append(temp)
maxp = 0
for i in range(1, n + 1):
	if li[i]:
		maxp += 1
	if li[i] == 2:
		(a, b) = (li2[i][0], li2[i][1])
		mtx[a][b] += 1
		mtx[b][a] += 1
	elif li[i] == 1:
		val = li2[i][0]
		for p in range(1, q + 1):
			if p != val:
				mtx[p][val] += 1
				mtx[val][p] += 1
minn = float('inf')
for i in range(1, q + 1):
	for j in range(i + 1, q + 1):
		minn = min(minn, mtx[i][j])
print(maxp - minn)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
LR = []
imos = [0] * (n + 1)
for i in range(q):
	(l, r) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	LR.append((l, r))
	imos[l] += 1
	imos[r + 1] -= 1
from itertools import accumulate
imos = list(accumulate(imos))
C = [0] * (n + 1)
for i in range(n):
	c = imos[i]
	C[i + 1] = C[i]
	if c == 1:
		C[i + 1] += 1
C2 = [0] * (n + 1)
for i in range(n):
	c = imos[i]
	C2[i + 1] = C2[i]
	if c == 2:
		C2[i + 1] += 1
s = 0
for i in range(n):
	if imos[i] > 0:
		s += 1
LR.sort()
ans = 0
for i in range(q - 1):
	(l1, r1) = LR[i]
	for j in range(i + 1, q):
		(l2, r2) = LR[j]
		if r1 < l2:
			c = C[r1 + 1] - C[l1] + C[r2 + 1] - C[l2]
		elif l2 <= r1 <= r2:
			c = C[l2 + 1] - C[l1] + C2[r1 + 1] - C2[l2] + C[r2 + 1] - C[r1]
		elif r2 < r1:
			c = C[l2 + 1] - C[l1] + C2[r2 + 1] - C2[l2] + C[r1 + 1] - C[r2]
		ans = max(ans, s - c)
print(ans)


import collections
(n, q) = map(int, input().split())
sections = [0] * n
p = []
for _ in range(q):
	(l, r) = 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)


import os
import sys
from io import BytesIO, IOBase
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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def toord(c):
	return ord(c) - ord('a')

def lcm(a, b):
	return a * b // lcm(a, b)
mod = 998244353
INF = float('inf')
from math import factorial, sqrt, ceil, floor, gcd
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	(n, q) = RL()
	arr = [RLL() for _ in range(q)]
	rec = [0] * (n + 1)
	for (l, r) in arr:
		for j in range(l, r + 1):
			rec[j] += 1
	res = 0
	for i in range(1, n + 1):
		if rec[i] > 0:
			res += 1
	ret = 0
	for i in range(q - 1):
		(l, r) = arr[i]
		tarr = rec.copy()
		tres = res
		for j in range(l, r + 1):
			tarr[j] -= 1
			if tarr[j] == 0:
				tres -= 1
		sm = [0]
		for j in range(1, n + 1):
			sm.append(sm[-1] + (1 if tarr[j] == 1 else 0))
		for j in range(i + 1, q):
			(jl, jr) = arr[j]
			ones = sm[jr] - sm[jl - 1]
			ret = max(ret, tres - ones)
	print(ret)
main()


def solve(N, Q, intervals):
	dp = [0] * (N + 1)
	L = [i + 1 for i in range(N + 1)]
	for (l, r) in intervals:
		for i in range(l, r + 1, 1):
			L[i] = min(L[i], l)
	for _ in range(Q - 2):
		for i in range(N, 0, -1):
			l = L[i]
			dp[i] = max(dp[i], dp[l - 1] + i - l + 1)
		for i in range(1, N + 1, 1):
			dp[i] = max(dp[i], dp[i - 1])
	return dp[N]
(N, Q) = map(int, input().split())
intervals = []
for _ in range(Q):
	(l, r) = map(int, input().split())
	intervals.append((l, r))
print(solve(N, Q, intervals))


from sys import stdin
input = stdin.readline

def solve():
	(n, q) = map(int, input().split())
	fences = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
	NINF = -5005
	dp = [[NINF] * 3 for _ in range(n + 2)]
	dp[1][0] = 0
	fences.sort()
	for (s, e) in fences:
		for x in range(n + 1, 0, -1):
			extra = max(0, e - max(s, x) + 1)
			end = max(e + 1, x)
			for skipped in range(2, -1, -1):
				if skipped != 2:
					dp[x][skipped + 1] = max(dp[x][skipped + 1], dp[x][skipped])
				dp[end][skipped] = max(dp[end][skipped], dp[x][skipped] + extra)
	print(max((dp[x][2] for x in range(1, n + 2))))
solve()


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

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

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, q) = li()
	a = [[] for i in range(n)]
	for i in range(q):
		(l, r) = li()
		for j in range(l - 1, r):
			a[j].append(i)
	count = [[0 for i in range(q)] for j in range(q)]
	ind = -1
	total = 0
	for i in a:
		if len(i) != 0:
			total += 1
		if len(i) == 1:
			for j in range(q):
				if j == i[0]:
					continue
				count[i[0]][j] += 1
				count[j][i[0]] += 1
		elif len(i) == 2:
			count[i[0]][i[1]] += 1
			count[i[1]][i[0]] += 1
	ans = -1
	for i in range(q):
		for j in range(i + 1, q):
			ans = max(ans, total - count[i][j])
	print(ans)
t = 1
for _ in range(t):
	solve()


(n, q) = map(int, input().split())
a = []
ar = [0 for i in range(n + 1)]
for i in range(q):
	(l, r) = 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)


import sys
input = sys.stdin.readline
for _ in range(1):
	(n, q) = map(int, input().split())
	visited = [0 for i in range(n + 1)]
	arr = []
	for i in range(q):
		(l, r) = map(int, input().split())
		for j in range(l, r + 1):
			visited[j] += 1
		arr.append((l, r))
	ans = 0
	for w in range(len(arr)):
		x = arr[w]
		ones = [0 for j in range(n + 1)]
		l = x[0]
		r = x[1]
		total = 0
		for i in range(l, r + 1):
			visited[i] -= 1
		for i in range(1, n + 1):
			if visited[i] > 0:
				total += 1
			if visited[i] == 1:
				ones[i] = 1
		for i in range(1, n + 1):
			ones[i] += ones[i - 1]
		for i in range(len(arr)):
			if i != w:
				y = arr[i]
				left = y[0]
				right = y[1]
				if left == 1:
					rip = ones[right]
				else:
					rip = ones[right] - ones[left - 1]
				ans = max(ans, total - rip)
		for i in range(l, r + 1):
			visited[i] += 1
	print(ans)


import os, sys
from io import BytesIO, IOBase

def main():
	(n, q) = map(int, input().split())
	dp = [0] * (n + 2)
	paint = [tuple(map(int, input().split())) for _ in range(q)]
	for i in paint:
		dp[i[0]] += 1
		dp[i[1] + 1] -= 1
	for i in range(1, n + 1):
		dp[i] += dp[i - 1]
	one = [0]
	two = [0]
	ans = 0
	for i in range(1, n + 1):
		ans += dp[i] != 0
		one.append(one[-1] + (dp[i] == 1))
		two.append(two[-1] + (dp[i] == 2))
	fin = 0
	for i in range(q):
		for j in range(i + 1, q):
			val = one[paint[j][1]] - one[paint[j][0] - 1] + one[paint[i][1]] - one[paint[i][0] - 1]
			(x, y) = (max(paint[j][0], paint[i][0]), min(paint[j][1], paint[i][1]))
			if x <= y:
				val -= one[y] - one[x - 1]
				val += two[y] - two[x - 1]
			fin = max(fin, ans - val)
	print(fin)
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()


import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
from itertools import combinations

def solve(n, _, lr):
	lr.sort()
	counts = [0] * (n + 1)
	for (l, r) in lr:
		for i in range(l, r + 1):
			counts[i] += 1
	(ones, twos) = ([], [])
	for (n, lst) in ((1, ones), (2, twos)):
		x = 0
		for c in counts:
			if c == n:
				x += 1
			lst.append(x)

	def get(lst, i, j):
		return lst[j] - lst[i - 1]
	(ep, base_s) = (0, 0)
	for (l, r) in lr:
		if ep < r:
			base_s += r - max(l, ep + 1) + 1
			ep = r
	min_s = base_s
	for (p, q) in combinations(lr, 2):
		if p[1] < q[0]:
			s = get(ones, *p) + get(ones, *q)
		elif p[1] > q[1]:
			s = get(ones, p[0], q[0] - 1) + get(twos, *q) + get(ones, q[1] + 1, p[1])
		else:
			s = get(ones, p[0], q[0] - 1) + get(twos, q[0], p[1]) + get(ones, p[1] + 1, q[1])
		min_s = min(min_s, s)
	print(base_s - min_s)

def solve_bf(n, q, lr):
	lr.sort()
	mxs = 0
	for c in combinations(lr, q - 2):
		(ep, s) = (0, 0)
		for (l, r) in c:
			if ep < r:
				s += r - max(l, ep + 1) + 1
				ep = r
		mxs = max(mxs, s)
	print(mxs)

def solve_from_stdin():
	(n, q) = map(int, input().split())
	lr = []
	for _ in range(q):
		(l, r) = map(int, input().split())
		lr.append((l, r))
	solve(n, q, lr)
solve_from_stdin()


from sys import exit, setrecursionlimit
setrecursionlimit(10 ** 6)
inn = lambda : input().strip()
mapp_m1 = lambda : map(lambda x: int(x) - 1, inn().split(' '))
mapp = lambda : map(int, inn().split(' '))
(N, Q) = mapp()
painter = []
for _ in range(Q):
	painter.append(tuple(mapp_m1()))
painter.sort()
makeFence = [0] * (N + 1)
for (l, r) in painter:
	makeFence[l] += 1
	makeFence[r + 1] -= 1
fence = [0] * N
fence[0] = makeFence[0]
for a in range(1, N):
	fence[a] = fence[a - 1] + makeFence[a]
(one, two, count) = ([0] * N, [0] * N, 0)
for a in range(N):
	if fence[a] == 1:
		one[a] = 1
	if fence[a] == 2:
		two[a] = 1
	if fence[a] != 0:
		count += 1
(pOne, pTwo) = ([0] * N, [0] * N)
pOne[0] = one[0]
pTwo[0] = two[0]
for a in range(1, N):
	pOne[a] = pOne[a - 1] + one[a]
	pTwo[a] = pTwo[a - 1] + two[a]

def rangeSum(psum, a, b):
	ret = 0
	if a == 0:
		ret = psum[b]
	else:
		ret = psum[b] - psum[a - 1]
	return ret
answer = 0
for p1 in range(Q):
	for p2 in range(p1 + 1, Q):
		(l1, r1) = painter[p1]
		(l2, r2) = painter[p2]
		cnt = count - rangeSum(pOne, l1, r1) - rangeSum(pOne, l2, r2)
		if l2 <= r1:
			cnt -= rangeSum(pTwo, l2, min(r1, r2))
		answer = max(cnt, answer)
print(answer)


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


from collections import defaultdict
(n, q) = 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):
	temp = 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:
			temp += 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, temp - b[a[j][1]] + b[a[j][0] - 1])
print(ans)


import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
print = lambda x: os.write(1, str(x).encode())
(n, q) = map(int, input().split())
(l, r) = ([0] * q, [0] * q)
p = [0] * n
for i in range(q):
	(l[i], r[i]) = map(int, input().split())
	for j in range(l[i] - 1, r[i]):
		p[j] += 1
(l, r) = [list(col) for col in zip(*sorted(zip(l, r)))]
zero_cnt = p.count(0)
(pref_sums_1, pref_sums_2) = ([0] * (n + 1), [0] * (n + 1))
for i in range(n):
	pref_sums_1[i + 1] = pref_sums_1[i] + int(p[i] == 1)
	pref_sums_2[i + 1] = pref_sums_2[i] + int(p[i] == 2)
res = 0
for i in range(q):
	for j in range(i + 1, q):
		if r[i] < l[j]:
			cnt = pref_sums_1[r[i]] + pref_sums_1[r[j]] - (pref_sums_1[l[i] - 1] + pref_sums_1[l[j] - 1])
		elif r[i] >= r[j]:
			cnt = pref_sums_1[l[j] - 1] + pref_sums_1[r[i]] + pref_sums_2[r[j]] - (pref_sums_1[l[i] - 1] + pref_sums_1[r[j]] + pref_sums_2[l[j] - 1])
		else:
			cnt = pref_sums_1[l[j] - 1] + pref_sums_1[r[j]] + pref_sums_2[r[i]] - (pref_sums_1[l[i] - 1] + pref_sums_1[r[i]] + pref_sums_2[l[j] - 1])
		res = max(res, n - cnt - zero_cnt)
print(res)


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


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
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')
(n, q) = map(int, input().split())
zab = [0] * 5001
a = []
for i in range(q):
	(l, r) = map(int, input().split())
	a.append([l, r])
	for j in range(l, r + 1):
		zab[j] += 1
ans = 0
for i in range(q):
	fl = 0
	d = zab.copy()
	for j in range(a[i][0], a[i][1] + 1):
		d[j] -= 1
	for j in range(5001):
		if d[j] > 0:
			fl += 1
	b = [0] * 5001
	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, fl - b[a[j][1]] + b[a[j][0] - 1])
print(ans)