Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

You have $C = 100,000$ cakes, numbered $1$ through $C$. Each cake has an integer height; initially, the height of each cake is $0$.

There are $N$ operations. In each operation, you are given two integers $L$ and $R$, and you should increase by $1$ the height of each of the cakes $L, L+1, \ldots, R$. One of these $N$ operations should be removed and the remaining $N-1$ operations are then performed.

Chef wants to remove one operation in such a way that after the remaining $N-1$ operations are performed, the number of cakes with height exactly $K$ is maximum possible. Since Chef is a bit busy these days, he has asked for your help. You need to find the maximum number of cakes with height exactly $K$ that can be achieved by removing one operation.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
Each of the next $N$ lines contains two space-separated integers $L$ and $R$ describing one operation.

------  Output ------
For each test case, print a single line containing one integer — the maximum possible number of cakes with height $K$.

------  Constraints  ------
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
$1 ≤ L ≤ R ≤ 10^{5}$
the sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
1
3 2
2 6
4 9
1 4
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
Example case 1: Let's look at what happens after an operation is removed.
- Removing operation $1$: The heights of cakes $4$ through $9$ increase by $1$. Then, the heights of cakes $1$ through $4$ increase by $1$. The resulting sequence of heights is $[1, 1, 1, 2, 1, 1, 1, 1, 1]$ (for cakes $1$ through $9$; the other cakes have heights $0$). The number of cakes with height $2$ is $1$.
- Removing operation $2$: The resulting sequence of heights of cakes $1$ through $9$ is $[1, 2, 2, 2, 1, 1, 0, 0, 0]$. The number of cakes with height $2$ is $3$.
- Removing operation $3$: The resulting sequence of heights of cakes $1$ through $9$ is $[0, 1, 1, 2, 2, 2, 1, 1, 1]$. The number of cakes with height $2$ is $3$.

The maximum number of cakes with height $2$ is $3$.

Difficulty: HARD
Tags: Constructive algorithms

Data structures

Range queries

Ad-hoc
Skill types: Data structures

Range queries

Starter code:

Solutions:
t = int(input())
for _ in range(int(t)):
	(n, k) = map(int, input().split())
	q = []
	sz = 0
	for i in range(n):
		(l, r) = map(int, input().split())
		q.append((l, r))
		sz = max(sz, r)
	arr = [0] * (sz + 2)
	k1 = [0] * (sz + 2)
	k2 = [0] * (sz + 2)
	for (l, r) in q:
		arr[l] += 1
		arr[r + 1] -= 1
	res = [0] * (sz + 2)
	res[0] = arr[0]
	for i in range(1, sz + 2):
		res[i] = arr[i] + res[i - 1]
		k1[i] = k1[i - 1]
		k2[i] = k2[i - 1]
		if res[i] == k:
			k1[i] += 1
		if res[i] == k + 1:
			k2[i] += 1
	ans = -1
	for (l, r) in q:
		kval = k1[r] - k1[l - 1]
		k1val = k2[r] - k2[l - 1]
		ans = max(ans, k1[-1] - kval + k1val, ans)
	print(ans)


c = 100000
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	dif = [0] * (c + 1)
	ans = [0] * c
	rmax = 0
	queries = []
	for i in range(n):
		(l, r) = map(int, input().split())
		queries.append([l, r])
		rmax = max(rmax, r)
		dif[l - 1] += 1
		dif[r] -= 1
	ans[0] = dif[0]
	s = [0] * (rmax + 1)
	m = [0] * (rmax + 1)
	for i in range(rmax):
		ans[i] = ans[i - 1] + dif[i]
		s[i + 1] = s[i]
		m[i + 1] = m[i]
		if ans[i] == k + 1:
			s[i + 1] += 1
		if ans[i] == k:
			m[i + 1] += 1
	result = 0
	total = m[-1]
	for (l, r) in queries:
		nk1 = s[r] - s[l - 1]
		nk = m[r] - m[l - 1]
		result = max(result, total + nk1 - nk)
	print(result)


def sol():
	(n, k) = map(int, input().split())
	a = []
	mx = 0
	for _ in range(n):
		(l, r) = map(int, input().split())
		mx = max(mx, r)
		a.append([l, r])
	ans = [0] * (mx + 2)
	prek = [0] * (mx + 2)
	prek1 = [0] * (mx + 2)
	for (l, r) in a:
		ans[l] += 1
		ans[r + 1] -= 1
	for i in range(1, mx + 1):
		ans[i] += ans[i - 1]
	for i in range(1, mx + 1):
		prek[i] = 1 if ans[i] == k else 0
		prek1[i] = 1 if ans[i] == k + 1 else 0
	for i in range(1, mx + 1):
		prek[i] += prek[i - 1]
		prek1[i] += prek1[i - 1]
	res = 0
	for (l, r) in a:
		res = max(res, prek[l - 1] + prek[mx] - prek[r] + prek1[r] - prek1[l - 1])
	print(res)

def main():
	for _ in range(int(input())):
		sol()
main()


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	q = []
	sz = 0
	for i in range(n):
		(l, r) = map(int, input().split())
		q.append((l, r))
		sz = max(sz, r)
	arr = [0] * (sz + 5)
	k1 = [0] * (sz + 5)
	k_1 = [0] * (sz + 5)
	for (l, r) in q:
		arr[l] += 1
		arr[r + 1] -= 1
	for i in range(1, sz + 5):
		arr[i] += arr[i - 1]
		k1[i] = k1[i - 1]
		k_1[i] = k_1[i - 1]
		if arr[i] == k:
			k1[i] += 1
		if arr[i] == k + 1:
			k_1[i] += 1
	maxm = -1
	for (l, r) in q:
		kval = k1[r] - k1[l - 1]
		k_1val = k_1[r] - k_1[l - 1]
		maxm = max(k1[-1] + k_1val - kval, maxm)
	print(maxm)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	queries = []
	mx = 0
	ans = 0
	for i in range(N):
		(l, r) = map(int, input().split())
		queries.append((l, r))
		mx = max(mx, r)
	final = [0] * (mx + 2)
	total_K = [0] * (mx + 2)
	total_K1 = [0] * (mx + 2)
	for (l, r) in queries:
		final[l] += 1
		final[r + 1] -= 1
	for i in range(1, len(final)):
		final[i] += final[i - 1]
		if final[i] == K:
			total_K[i] += 1
		if final[i] == K + 1:
			total_K1[i] += 1
	for i in range(1, len(total_K)):
		total_K[i] += total_K[i - 1]
		total_K1[i] += total_K1[i - 1]
	for (l, r) in queries:
		temp = total_K[-1] - (total_K[r] - total_K[l - 1]) + (total_K1[r] - total_K1[l - 1])
		ans = max(ans, temp)
	print(ans)


for _ in range(int(input())):
	query = []
	(n, k) = [int(i) for i in input().split()]
	mx = 0
	for _ in range(n):
		(l, r) = [int(i) for i in input().split()]
		query.append((l, r))
		mx = max(mx, r)
	arr = [0] * (mx + 2)
	arrk = [0] * (mx + 2)
	arrk1 = [0] * (mx + 2)
	for (l, r) in query:
		arr[l] += 1
		arr[r + 1] -= 1
	for i in range(mx + 1):
		arr[i + 1] += arr[i]
		if arr[i + 1] == k:
			arrk[i + 1] += 1
		if arr[i + 1] == k + 1:
			arrk1[i + 1] += 1
	for i in range(mx + 1):
		arrk[i + 1] += arrk[i]
		arrk1[i + 1] += arrk1[i]
	total = 0
	for (l, r) in query:
		sub_total = arrk[-1] - (arrk[r] - arrk[l - 1]) + (arrk1[r] - arrk1[l - 1])
		total = max(total, sub_total)
	print(total)


t = int(input().strip())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = []
	sb = []
	mx = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append((x, y))
		mx = max(mx, y)
	a = []
	a = [0 for i in range(mx + 1)]
	for t in l:
		a[t[0] - 1] += 1
		a[t[1]] -= 1
	for i in range(1, mx):
		a[i] += a[i - 1]
	kPlusOneArray = [0] * mx
	kArray = [0] * mx
	for i in range(mx):
		if a[i] == k:
			kArray[i] = 1
		if a[i] == k + 1:
			kPlusOneArray[i] = 1
	for i in range(1, mx):
		kArray[i] = kArray[i] + kArray[i - 1]
		kPlusOneArray[i] = kPlusOneArray[i] + kPlusOneArray[i - 1]
	ans = 0
	for tuple in l:
		if tuple[0] > 1:
			kPlusOneAns = kPlusOneArray[tuple[1] - 1] - kPlusOneArray[tuple[0] - 2]
			kAns = kArray[tuple[1] - 1] - kArray[tuple[0] - 2]
		else:
			kPlusOneAns = kPlusOneArray[tuple[1] - 1]
			kAns = kArray[tuple[1] - 1]
		if ans < kArray[mx - 1] + kPlusOneAns - kAns:
			ans = kArray[mx - 1] + kPlusOneAns - kAns
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	left = []
	right = []
	mx = 0
	for i in range(n):
		(l, r) = map(int, input().split(' '))
		left.append(l)
		right.append(r)
		mx = max(mx, r)
	total = [0] * (mx + 2)
	s = [0] * (mx + 2)
	po = [0] * (mx + 2)
	q = [0] * (mx + 2)
	for i in range(n):
		total[left[i]] += 1
		total[right[i] + 1] += -1
	for i in range(1, mx + 2):
		total[i] = total[i] + total[i - 1]
		q[i] = (total[i] == k + 1) + q[i - 1]
		s[i] = (total[i] == k) + s[i - 1]
	ac = 0
	for i in reversed(range(1, mx + 1)):
		po[i] = po[i + 1] + (total[i] == k)
	for i in range(n):
		x = left[i]
		y = right[i]
		cnt = q[y] - q[x] + (total[x] == k + 1)
		cnt += s[x - 1] + po[y + 1]
		ac = max(ac, cnt)
	print(ac)


t = int(input().strip())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = []
	m = 0
	for _ in range(n):
		(l, r) = map(int, input().split())
		a.append([l, r])
		m = max(m, r)
	a1 = [0] * (m + 2)
	a2 = [0] * (m + 2)
	a3 = [0] * (m + 2)
	for j in range(n):
		a1[a[j][0]] += 1
		a1[a[j][1] + 1] -= 1
	for j in range(1, m + 2, 1):
		a1[j] = a1[j - 1] + a1[j]
	for j in range(m + 2):
		if a1[j] == k:
			a2[j] = 1
		if a1[j] == k + 1:
			a3[j] = 1
	for j in range(1, m + 2, 1):
		a2[j] = a2[j - 1] + a2[j]
		a3[j] = a3[j - 1] + a3[j]
	maxi = 0
	for i in range(n):
		tt = 0
		t1 = a2[a[i][1]] - a2[a[i][0] - 1]
		tt += a2[m] - t1
		t1 = a3[a[i][1]] - a3[a[i][0] - 1]
		tt += t1
		maxi = max(maxi, tt)
	print(maxi)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = []
	max_r = 0
	for i in range(n):
		(l, r) = [int(x) for x in input().split()]
		max_r = max(max_r, r)
		a.append([l, r])
	max_r += 2
	change = [0] * max_r
	for i in a:
		change[i[0]] += 1
		change[i[1] + 1] -= 1
	for i in range(1, len(change)):
		change[i] += change[i - 1]
	mxk = 0
	kar = [0] * max_r
	kpar = [0] * max_r
	for i in range(len(change)):
		if change[i] == k:
			kar[i] += 1
		if change[i] == k + 1:
			kpar[i] += 1
	for i in range(1, len(change)):
		kar[i] += kar[i - 1]
		kpar[i] += kpar[i - 1]
	for i in a:
		(l, r) = (i[0], i[1])
		sayavar = kar[-1] - (kar[r] - kar[l - 1]) + (kpar[r] - kpar[l - 1])
		mxk = max(mxk, sayavar)
	print(mxk)


def max_range(n, k, l):
	max = 0
	h = 0
	x = 0
	y = 0
	p = 0
	q = 0
	f = l[0][0]
	g = l[0][1]
	cake = [0] * 100000
	for node in range(n):
		cake[l[node][0] - 1] += 1
		cake[l[node][1]] -= 1
		if l[node][0] < f:
			f = l[node][0]
		if l[node][1] > g:
			g = l[node][1]
	c = [0] * (g - f + 2)
	for i in range(f - 1, g + 1):
		if h + cake[i] == k + 1:
			c[i - (f - 1)] = q + 1
			q += 1
		else:
			c[i - (f - 1)] = q
		if h + cake[i] == k:
			x += 1
			h = h + cake[i]
			cake[i] = p + 1
			p += 1
		else:
			h = h + cake[i]
			cake[i] = p
	for node in range(n):
		count = 0
		if l[node][0] == 1:
			count = c[l[node][1] - 1 - (f - 1)] + x - cake[l[node][1] - 1]
		else:
			count = c[l[node][1] - 1 - (f - 1)] - c[l[node][0] - 2 - (f - 1)] + x - (cake[l[node][1] - 1] - cake[l[node][0] - 2])
		if count > max:
			max = count
	return max
t = int(input())
for x in range(t):
	s = input().split(' ')
	N = int(s[0])
	K = int(s[1])
	l = []
	for i in range(N):
		l1 = []
		s = input().split(' ')
		l1.append(int(s[0]))
		l1.append(int(s[1]))
		l.append(l1)
	result = max_range(N, K, l)
	print(result)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = []
	maxr = -1
	c = [0] * 100001
	for _ in range(n):
		(l, r) = map(int, input().split())
		maxr = max(r, maxr)
		c[l] += 1
		c[r + 1] -= 1
		a.append((l, r))
	count = 0
	pre = [0] * (maxr + 1)
	pre2 = [0] * (maxr + 1)
	for i in range(1, maxr + 1):
		c[i] += c[i - 1]
		if c[i] == k:
			pre[i] = 1
		if c[i] == k + 1:
			pre2[i] = 1
		pre[i] += pre[i - 1]
		pre2[i] += pre2[i - 1]
	totk = pre[-1]
	ans = 0
	for i in range(n):
		ck = pre[a[i][1]] - pre[a[i][0] - 1]
		ck1 = pre2[a[i][1]] - pre2[a[i][0] - 1]
		count = totk - ck + ck1
		ans = max(ans, count)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	x = [0] * 100001
	maxi_r = 0
	for _ in range(n):
		(L, R) = map(int, input().split())
		if R > maxi_r:
			maxi_r = R
		l.append((L, R))
		x[L] += 1
		x[R + 1] -= 1
	maxi_r += 2
	x = x[:maxi_r]
	yk = [0] * maxi_r
	zkk = [0] * maxi_r
	for i in range(1, maxi_r):
		x[i] = x[i - 1] + x[i]
	for i in range(1, maxi_r):
		if x[i] == k:
			yk[i] = yk[i - 1] + 1
		else:
			yk[i] = yk[i - 1]
		if x[i] == k + 1:
			zkk[i] = zkk[i - 1] + 1
		else:
			zkk[i] = zkk[i - 1]
	m = 0
	for (i, j) in l:
		r1 = yk[j] - yk[i - 1]
		r2 = zkk[j] - zkk[i - 1]
		r = r2 - r1
		n = yk[-1] + r
		if n > m:
			m = n
	print(m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [0] * (10 ** 5 + 1)
	op = []
	ans = 0
	maxi = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		maxi = max(b, maxi)
		op.append([a, b])
		l[a] += 1
		l[b + 1] -= 1
	arr = [0] * (maxi + 1)
	for i in range(1, maxi + 1):
		arr[i] = arr[i - 1] + l[i]
	count = 0
	freq = [0] * (maxi + 1)
	freq1 = [0] * (maxi + 1)
	for i in range(1, maxi + 1):
		freq[i] = freq[i - 1]
		freq1[i] = freq1[i - 1]
		if arr[i] == k:
			freq[i] += 1
		elif arr[i] == k + 1:
			freq1[i] += 1
	val = arr.count(k)
	for i in range(n):
		cou = freq[op[i][1]] - freq[op[i][0] - 1]
		cou1 = freq1[op[i][1]] - freq1[op[i][0] - 1]
		count = val - cou + cou1
		if count > ans:
			ans = count
	print(ans)


t = int(input())
while t > 0:
	t = t - 1
	(n, k) = map(int, input().split())
	h = []
	le = []
	r = []
	mr = 0
	for i in range(0, n):
		(l, ri) = map(int, input().split())
		le.append(l)
		r.append(ri)
		if ri > mr:
			mr = ri
	for i in range(0, mr + 2):
		h.append(0)
	for i in range(0, n):
		h[le[i]] += 1
		h[r[i] + 1] += -1
	for i in range(1, mr + 1):
		h[i] = h[i] + h[i - 1]
	he = []
	hu = []
	if h[0] == k:
		he.append(1)
		y = 1
	else:
		he.append(0)
		y = 0
	if h[0] == k + 1:
		hu.append(1)
	else:
		hu.append(0)
	for i in range(1, mr + 1):
		if h[i] == k:
			he.append(he[i - 1] + 1)
			y = y + 1
		else:
			he.append(he[i - 1])
		if h[i] == k + 1:
			hu.append(hu[i - 1] + 1)
		else:
			hu.append(hu[i - 1])
	check = []
	for i in range(0, n):
		check.append(he[r[i]] - he[le[i] - 1] - (hu[r[i]] - hu[le[i] - 1]))
	max = 0
	for i in range(0, n):
		x = y - check[i]
		if x > max:
			max = x
	print(max)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lt = []
	freq = [0] * 100003
	maxi = -1
	for _ in range(n):
		(l, r) = map(int, input().split())
		lt.append((l, r))
		freq[l] += 1
		freq[r + 1] -= 1
		maxi = max(maxi, r)
	for i in range(1, maxi + 1):
		freq[i] = freq[i - 1] + freq[i]
	prefix_k = [0] * (maxi + 1)
	prefix_k_plus = [0] * (maxi + 1)
	for i in range(1, maxi + 1):
		prefix_k[i] = prefix_k[i - 1]
		if freq[i] == k:
			prefix_k[i] += 1
	for i in range(1, maxi + 1):
		prefix_k_plus[i] = prefix_k_plus[i - 1]
		if freq[i] == k + 1:
			prefix_k_plus[i] += 1
	idx = 0
	curr_k = 0
	for i in range(n):
		l = lt[i][0]
		r = lt[i][1]
		local_k = prefix_k[-1] - prefix_k[r] + prefix_k[l - 1] + prefix_k_plus[r] - prefix_k_plus[l - 1]
		curr_k = max(local_k, curr_k)
	print(curr_k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	maxlen = 0
	for _ in range(n):
		(l, r) = map(int, input().split())
		a.append((l, r))
		maxlen = max(maxlen, r)
	cakes = [0] * (maxlen + 2)
	for i in a:
		(l, r) = (i[0], i[1])
		cakes[l - 1] += 1
		cakes[r] -= 1
	for i in range(1, len(cakes)):
		cakes[i] += cakes[i - 1]
	b = []
	d = []
	c = 0
	f = 0
	result = 0
	for i in range(len(cakes)):
		if cakes[i] == k:
			c += 1
		if cakes[i] == k + 1:
			f += 1
		b.append(c)
		d.append(f)
	for i in range(n):
		(l, r) = (a[i][0], a[i][1])
		nk = b[r - 1] - (0 if l == 1 else b[l - 2])
		nk1 = d[r - 1] - (0 if l == 1 else d[l - 2])
		tnk = nk1 - nk
		result = max(result, c + tnk)
	print(result)


cpc = [0 for i in range(100001)]
cqc = [0 for i in range(100001)]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [0 for i in range(100001)]
	check = []
	lr = 0
	for i in range(n):
		(l, r) = map(int, input().split())
		check.append((l, r))
		lr = max(r, lr)
		arr[l] += 1
		r += 1
		if r <= 100000:
			arr[r] -= 1
	ans = 0
	cpc[1] = 0
	cqc[1] = 0
	if arr[1] == k:
		cpc[1] += 1
		ans += 1
	elif arr[1] == k + 1:
		cqc[1] += 1
	for i in range(2, lr + 1):
		arr[i] += arr[i - 1]
		cpc[i] = 0
		cpc[i] += cpc[i - 1]
		cqc[i] = 0
		cqc[i] += cqc[i - 1]
		if arr[i] == k:
			ans += 1
			cpc[i] += 1
		elif arr[i] == k + 1:
			cqc[i] += 1
	m = 0
	for i in range(n):
		(l, r) = (check[i][0], check[i][1])
		m = max(m, ans - (cpc[r] - cpc[l - 1]) + (cqc[r] - cqc[l - 1]))
	print(m)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	l = [0] * n
	r = [0] * n
	for i in range(n):
		(a, b) = map(int, input().split())
		l[i] = a
		r[i] = b
	MAX = max(r) + 2
	psum = [0] * MAX
	for i in range(n):
		psum[l[i]] += 1
		psum[r[i] + 1] -= 1
	for i in range(1, MAX):
		psum[i] = psum[i] + psum[i - 1]
	psk = [0] * MAX
	pskp = [0] * MAX
	for i in range(1, MAX):
		if psum[i] == k:
			psk[i] = psk[i - 1] + 1
		else:
			psk[i] = psk[i - 1]
		if psum[i] == k + 1:
			pskp[i] = pskp[i - 1] + 1
		else:
			pskp[i] = pskp[i - 1]
	mk = -1000000
	for i in range(n):
		nk = psk[r[i]] - psk[l[i] - 1]
		nkp = pskp[r[i]] - pskp[l[i] - 1]
		mk = max(mk, -nk + nkp)
	print(psk[MAX - 1] + mk)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	queries = []
	p = [0] * 100007
	max_r = -1
	for j in range(n):
		(l, r) = map(int, input().split(' '))
		max_r = max(max_r, r)
		queries.append([l, r])
		p[l] += 1
		p[r + 1] -= 1
	for j in range(1, max_r + 1):
		p[j] += p[j - 1]
	results = [0] * (max_r + 2)
	dp = [0] * (max_r + 2)
	count = countk = 0
	for j in range(1, max_r + 1):
		countk = 0
		count = 0
		if p[j] == k + 1:
			countk = 1
		if p[j] == k:
			count = 1
		results[j] = results[j - 1] + count
		dp[j] = dp[j - 1] + countk
	values = 0
	for j in range(len(queries)):
		temp = results[-2] + dp[queries[j][1]] - dp[queries[j][0] - 1] - results[queries[j][1]] + results[queries[j][0] - 1]
		values = max(values, temp)
	print(values)
	del dp, p, queries, results


for _ in range(int(input())):
	ma = 100009
	(n, k) = map(int, input().split())
	mat = []
	mind = 0
	for i in range(n):
		(l, r) = map(int, input().split())
		mat.append([l, r])
		mind = max(mind, r)
	ma = mind + 5
	couk = [0 for i in range(ma)]
	for i in range(n):
		(l, r) = (mat[i][0], mat[i][1])
		couk[l] += 1
		couk[r + 1] -= 1
	pre = [0 for i in range(ma)]
	pre2 = [0 for i in range(ma)]
	for i in range(1, ma):
		couk[i] = couk[i - 1] + couk[i]
		if couk[i] == k:
			pre[i] = 1
		if couk[i] == k + 1:
			pre2[i] = 1
		pre[i] += pre[i - 1]
		pre2[i] += pre2[i - 1]
	total_k = pre[ma - 1]
	ans = 0
	for i in range(n):
		ck = pre[mat[i][1]] - pre[mat[i][0] - 1]
		ck1 = pre2[mat[i][1]] - pre2[mat[i][0] - 1]
		temp = ck1 - ck + total_k
		ans = max(ans, temp)
	print(ans)


t = int(input())
for i in range(t):
	ma = 0
	P = []
	(n, k) = map(int, input().split())
	for j in range(n):
		(a, b) = map(int, input().split())
		if b > ma:
			ma = b
		P.append([a, b])
	Arr = [0] * (ma + 5)
	for j in P:
		Arr[j[0]] += 1
		Arr[j[1] + 1] -= 1
	for j in range(1, len(Arr)):
		Arr[j] = Arr[j - 1] + Arr[j]
	Arr2 = [0] * (ma + 5)
	Arr3 = [0] * (ma + 5)
	for j in range(len(Arr)):
		if Arr[j] == k:
			Arr2[j] = 1
		if Arr[j] == k + 1:
			Arr3[j] = 1
	for j in range(1, len(Arr)):
		Arr2[j] = Arr2[j - 1] + Arr2[j]
		Arr3[j] = Arr3[j - 1] + Arr3[j]
	ma2 = 0
	for j in P:
		tot = 0
		her = Arr2[j[1]] - Arr2[j[0] - 1]
		tot += Arr2[ma] - her
		her2 = Arr3[j[1]] - Arr3[j[0] - 1]
		tot += her2
		if ma2 < tot:
			ma2 = tot
	print(ma2)


sz = 100001
t = int(input())
for test in range(t):
	(n, k) = map(int, input().split())
	(end, start) = ([0] * n, [0] * n)
	(sfx, pfx, dp) = ([0] * sz, [0] * sz, [0] * sz)
	ul = 0
	for i in range(n):
		(l, r) = map(int, input().split())
		ul = max(ul, r)
		dp[l - 1] += 1
		dp[r] -= 1
		start[i] = l - 1
		end[i] = r - 1
	a = [0] * (ul + 1)
	a[0] = dp[0]
	ans = 0
	if a[0] == k:
		pfx[0] = 1
		ans += 1
	elif a[0] == k + 1:
		sfx[0] = 1
	for i in range(1, ul):
		dp[i] += dp[i - 1]
		a[i] += dp[i]
		if a[i] == k:
			pfx[i] = pfx[i - 1] + 1
			ans += 1
		else:
			pfx[i] = pfx[i - 1]
		if a[i] == k + 1:
			sfx[i] = sfx[i - 1] + 1
		else:
			sfx[i] = sfx[i - 1]
	mx = -100001
	for i in range(n):
		l = start[i]
		r = end[i]
		tot = sfx[r] - sfx[l - 1]
		tot = tot - (pfx[r] - pfx[l - 1])
		mx = max(mx, tot)
	print(ans + mx)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = {0: 0}
	arr = []
	for i in range(n):
		(l, r) = map(int, input().split())
		arr.append([l, r])
		d[l] = d.get(l, 0) + 1
		d[r + 1] = d.get(r + 1, 0) - 1
	b = sorted(d)
	s = 0
	for i in b:
		d[i] = d[i] + s
		s = d[i]
	d1 = {}
	s = 0
	s1 = 0
	ans = 0
	for i in range(len(b) - 1):
		if d[b[i]] == k:
			ans += b[i + 1] - b[i]
	d1[0] = [0, 0]
	for i in range(len(b) - 1):
		if d[b[i]] == k:
			d1[b[i + 1]] = [d1[b[i]][0] + b[i + 1] - b[i], d1[b[i]][1]]
		else:
			d1[b[i + 1]] = [d1[b[i]][0], d1[b[i]][1]]
		if d[b[i]] == k + 1:
			d1[b[i + 1]] = [d1[b[i + 1]][0], d1[b[i]][1] + b[i + 1] - b[i]]
		else:
			d1[b[i + 1]] = [d1[b[i + 1]][0], d1[b[i]][1]]
	m = -1
	for i in arr:
		l = i[0]
		r = i[1]
		m = max(m, ans + d1[r + 1][1] - d1[l][1] - d1[r + 1][0] + d1[l][0])
	print(m)


import bisect

def find(arr, margin):
	if len(arr) == 0:
		return 0
	(l, r) = margin
	if arr[0] > r or arr[-1] < l:
		return 0
	r_ans = bisect.bisect_right(arr, r) - 1
	l_ans = bisect.bisect_left(arr, l)
	return r_ans - l_ans + 1

def main():
	for _ in range(int(input())):
		c = [0 for i in range(100002)]
		(n, k) = map(int, input().split())
		ops = []
		for i in range(n):
			(l, r) = map(int, input().split())
			ops.append((l, r))
			c[l] += 1
			c[r + 1] -= 1
		for i in range(2, 100001):
			c[i] += c[i - 1]
		(ks, kplus) = ([], [])
		for i in range(1, 100001):
			if c[i] == k:
				ks.append(i)
			elif c[i] == k + 1:
				kplus.append(i)
		op = ops[0]
		best = len(ks) - find(ks, op) + find(kplus, op)
		for op in ops[1:]:
			best = max(best, len(ks) - find(ks, op) + find(kplus, op))
		print(best)
main()


import math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
mod = 10 ** 9 + 7

def modu(a, m):
	if a % m:
		return a % m
	return m

def mindiff(a):
	b = a[:]
	b.sort()
	m = 10000000000
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] < m:
			m = b[i + 1] - b[i]
	return m

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

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1

def binsearch(arr, b, low, high):
	if low == high:
		return low
	if arr[math.ceil((low + high) / 2)] < b:
		return binsearch(arr, b, low, math.ceil((low + high) / 2) - 1)
	else:
		return binsearch(arr, b, math.ceil((low + high) / 2), high)

def ncr1(n, r):
	s = 1
	for i in range(min(n - r, r)):
		s *= n - i
		s %= mod
		s *= pow(i + 1, mod - 2, mod)
		s %= mod
	return s

def calc(n, m, r):
	s = 0
	for i in range(0, r + 1, 2):
		s += ncr1(n, i) * ncr1(m, i)
		s %= mod
	return s
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = {0: 0}
	arr = []
	for i in range(n):
		(l, r) = map(int, input().split())
		arr.append([l, r])
		d[l] = d.get(l, 0) + 1
		d[r + 1] = d.get(r + 1, 0) - 1
	b = sorted(d)
	s = 0
	for i in b:
		d[i] = d[i] + s
		s = d[i]
	d1 = {}
	s = 0
	s1 = 0
	ans = 0
	for i in range(len(b) - 1):
		if d[b[i]] == k:
			ans += b[i + 1] - b[i]
	d1[0] = [0, 0]
	for i in range(len(b) - 1):
		if d[b[i]] == k:
			d1[b[i + 1]] = [d1[b[i]][0] + b[i + 1] - b[i], d1[b[i]][1]]
		else:
			d1[b[i + 1]] = [d1[b[i]][0], d1[b[i]][1]]
		if d[b[i]] == k + 1:
			d1[b[i + 1]] = [d1[b[i + 1]][0], d1[b[i]][1] + b[i + 1] - b[i]]
		else:
			d1[b[i + 1]] = [d1[b[i + 1]][0], d1[b[i]][1]]
	m = -1
	for i in arr:
		l = i[0]
		r = i[1]
		m = max(m, ans + d1[r + 1][1] - d1[l][1] - d1[r + 1][0] + d1[l][0])
	print(m)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	m = 0
	options = []
	for i in range(n):
		(l, r) = map(int, input().split())
		options.append([l, r])
		m = max(m, l, r)
	m += 2
	c = [0] * m
	for i in options:
		c[i[0]] += 1
		c[i[1] + 1] -= 1
	x = 0
	w = []
	for i in range(m):
		x += c[i]
		w.append(x)
	c1 = [0] * m
	c2 = [0] * m
	for i in range(1, m):
		if w[i] == k:
			c1[i] = 1 + c1[i - 1]
		else:
			c1[i] = c1[i - 1]
	d1 = [0] * m
	for i in range(1, m):
		if w[i] == k + 1:
			d1[i] = 1 + d1[i - 1]
		else:
			d1[i] = d1[i - 1]
	for i in range(m - 2, 0, -1):
		if w[i] == k:
			c2[i] = 1 + c2[i + 1]
		else:
			c2[i] = c2[i + 1]
	mymax = 0
	for i in options:
		mymax = max(mymax, c1[i[0] - 1] + c2[i[1] + 1] + d1[i[1]] - d1[i[0] - 1])
	print(mymax)