Read problems statements in Mandarin Chinese  and Russian. 

Oh, no! Chef’s in trouble. He’s got himself stuck in a cave (we don’t know how) and is looking for a way out. The bigger problem is that he needs to get his tractor out of the cave (don't ask why Chef owns a tractor!). He currently faces a large block of height N cells and length N cells, and needs to get his tractor across this block. The block is made up of vertical columns of soil, each of which is one cell long. Each column has a continuous vertical gap, with the i^{th} column having its gap from the l_{i}^{th} cell to the h_{i}^{th} cell (starting from the bottom, 0-indexing). That is, in the i^{th} column, there is no soil from the l_{i}^{th} cell to the h_{i}^{th} cell (both inclusive). Chef can build additional gaps by clearing some cells of soil. His tractor has height H, and therefore, he needs to build a horizontal corridor of height H passing through all the columns. That is, some consecutive H rows must have no soil. Please see the figures in the example and explanation sections for more details.
Chef is able to clear one cell of soil by spending one unit of energy. Chef is smart, and will figure out a way to build the horizontal corridor while spending the minimum possible amount of energy. To estimate how many of his tasty dishes he will still be able to cook for you tonight, find out what is the minimum possible energy he needs to spend.

------ Input ------ 

First line of input contains one integer T - number of test cases. T test cases follow.
Each test case starts with two integers N and H – size of the cave and height of the tractor, respectively. In each of the next N lines are two integers l_{i} and h_{i}, respectively indicating lowest and highest number of cell for the gap in the i^{th} column.

------ Output ------ 

One integer – minimum energy required.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{6}$
$1 ≤ sum of N over all test cases ≤ 10^{6}$
$1 ≤ H ≤ N$
$0 ≤ l_{i} ≤ h_{i} < N$

------ Subtasks ------ 

Subtask 1 (25 points): T ≤ 100, N ≤ 100
Subtask 2 (75 points): No additional constraints

----- Sample Input 1 ------ 
2

4 3

1 2

1 2

1 2

1 2

5 2

2 3

1 2

2 3

1 2

2 3
----- Sample Output 1 ------ 
4

2
----- explanation 1 ------ 
In the second case, the figure describes the initial map, where white cells denote empty cells and brown cells denote soil cells.

When we removed soil in two cells as the following figure, then we can make a corridor of height 2, adn this is the optimal way to make a corridor.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Range queries

Segment trees revisited
Skill types: Dynamic programming

Data structures

Range queries

Starter code:

Solutions:
from itertools import accumulate
l = int(input())
for i in range(l):
	(n, h) = input().split()
	n = int(n)
	h = int(h)
	sum_list = [n] * n
	range_list = [0] * n
	for j in range(n):
		(h1, h2) = input().split()
		h1 = int(h1)
		h2 = int(h2)
		range_list[h1] -= 1
		if h2 + 1 < n:
			range_list[h2 + 1] += 1
	sum_range = list(accumulate(range_list))
	sum_list = [x + y for (x, y) in zip(sum_list, sum_range)]
	sum_final = [sum(sum_list[0:h])]
	for j in range(h, n):
		sum_final.append(sum_final[-1] + sum_list[j] - sum_list[j - h])
	print(min(sum_final))


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	dp = []
	dp = [0] * (n + 2)
	for i in range(n):
		(a, b) = map(int, input().split())
		dp[a + 1] -= 1
		dp[b + 2] += 1
	for i in range(1, n + 1):
		dp[i] += dp[i - 1]
	m = n * k
	mi = n * k
	s = sum(dp[1:1 + k])
	mi = min(s + m, mi)
	for i in range(2, n - k + 2):
		s = s - dp[i - 1] + dp[i + k - 1]
		mi = min(s + m, mi)
	print(mi)


for t in range(int(input())):
	(n, h) = map(int, input().split())
	l = [0] * (n + 2)
	s = 0
	ans = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		l[a + 1] -= 1
		l[b + 2] += 1
	l[0] = n
	for i in range(n):
		l[i + 1] += l[i]
	for i in range(n):
		l[i + 1] += l[i]
	print(min((l[i] - l[i - h] for i in range(h, n + 1))))


for h in range(int(input())):
	(n, height) = map(int, input().strip().split())
	end = [0 for i in range(n)]
	start = [0 for i in range(n)]
	row = [0 for i in range(n)]
	for i in range(n):
		(L, H) = map(int, input().strip().split())
		start[L] += 1
		end[H] += 1
	row[0] = start[0]
	for i in range(1, n):
		row[i] = row[i - 1] + start[i] - end[i - 1]
	maxi = sum(row[:height])
	sumi = maxi
	for i in range(height - 1, n - 1):
		sumi = sumi + row[i + 1] - row[i - height + 1]
		if sumi > maxi:
			maxi = sumi
	print(n * height - maxi)


for cas in range(int(input())):
	(n, h) = map(int, input().strip().split())
	row = [0] * (n + 2)
	for i in range(n):
		(a, b) = map(int, input().strip().split())
		row[a + 1] -= 1
		row[b + 2] += 1
	row[0] = n
	for i in range(n):
		row[i + 1] += row[i]
	for i in range(n):
		row[i + 1] += row[i]
	print(min((row[i] - row[i - h] for i in range(h, n + 1))))


__author__ = 'Om Kumar Sahoo'
cases = int(input())
for i in range(cases):
	(n, h) = [int(x) for x in input().split()]
	current = [0] * (n + 1)
	for j in range(n):
		(a, b) = [int(x) for x in input().split()]
		current[a] += 1
		current[b + 1] -= 1
	for j in range(1, n + 1):
		current[j] += current[j - 1]
	temp = 0
	for k in range(0, h):
		temp = temp + current[k]
	max = temp
	for j in range(1, n - h + 1):
		temp = temp - current[j - 1] + current[j - 1 + h]
		if temp > max:
			max = temp
	print(n * h - max)


test = int(input())
for _ in range(test):
	(n, h) = map(int, input().split())
	l = [0] * n
	s = 0
	ans = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		l[a] -= 1
		if b != n - 1:
			l[b + 1] += 1
	l[0] += n
	for i in range(1, n):
		l[i] += l[i - 1]
	for i in range(1, n):
		l[i] += l[i - 1]
	minx = l[h - 1]
	for i in range(h, n):
		minx = min(minx, l[i] - l[i - h])
	print(minx)


t = int(input())
for _ in range(t):
	(n, g) = map(int, input().split())
	a = [0 for i in range(n + 1)]
	for i in range(n):
		(l, h) = map(int, input().split())
		a[l] += 1
		a[h + 1] -= 1
	for i in range(1, n):
		a[i] += a[i - 1]
	for i in range(1, n):
		a[i] += a[i - 1]
	a = [0] + a
	m = -1
	for i in range(n - g + 1):
		m = max(m, a[i + g] - a[i])
	print(n * g - m)


t = int(input())
for i in range(t):
	(n, hi) = map(int, input().split())
	a = [0 for j in range(n + 1)]
	for j in range(n):
		(l, h) = map(int, input().split())
		a[l] += 1
		a[h + 1] -= 1
	for j in range(1, n):
		a[j] += a[j - 1]
	for j in range(1, n):
		a[j] += a[j - 1]
	a = [0] + a
	m = -1
	for j in range(n - hi + 1):
		m = max(m, a[j + hi] - a[j])
	print(n * hi - m)


t = int(input())
while t > 0:
	(n, h) = [int(i) for i in input().split()]
	dp = [0] * (n + 2)
	for i in range(n):
		(x, y) = [int(i) + 1 for i in input().split()]
		dp[0] += 1
		dp[x] -= 1
		dp[y + 1] += 1
	for i in range(1, n + 1):
		dp[i] += dp[i - 1]
	dp[0] = 0
	for i in range(2, n + 1):
		dp[i] += dp[i - 1]
	Min = 10000000000000
	for i in range(h, n + 1):
		Min = min(Min, dp[i] - dp[i - h])
	print(Min)
	t -= 1


import sys

def solve(gaps, N, H):
	ant = 0
	for i in range(N):
		gaps[i] = ant + gaps[i]
		ant = gaps[i]
	minimo = 0
	for i in range(H):
		minimo += N - gaps[i]
	suma = minimo
	for i in range(H, N):
		suma = suma - (N - gaps[i - H]) + (N - gaps[i])
		minimo = min(minimo, suma)
	return minimo
T = int(input())
for i in range(T):
	line = input()
	lista = [int(x) for x in line.split()]
	N = lista[0]
	H = lista[1]
	gaps = [0] * (N + 1)
	for i in range(N):
		line = input()
		lista = [int(x) for x in line.split()]
		gaps[lista[0]] += 1
		gaps[lista[1] + 1] -= 1
	print(solve(gaps, N, H))


from collections import deque

class WayOut(object):

	def __init__(self, N, H):
		self._N = N
		self._H = H
		self._cells = [0] * N
		self._intervals = []

	def _AddCell(self, i, start, end):
		self._intervals.append((start, 'start', i))
		self._intervals.append((end + 1, 'end', i))

	def _GetHorizontalSum(self, w):
		return self._N - self._cells[w]

	def _Process(self):
		intervals_deque = deque(sorted(self._intervals))
		intervals_dict = {}
		for n in range(self._N):
			while intervals_deque:
				interval = intervals_deque.popleft()
				if interval[0] == n and interval[1] == 'end':
					del intervals_dict[interval[2]]
					continue
				else:
					intervals_deque.appendleft(interval)
					break
			while intervals_deque:
				interval = intervals_deque.popleft()
				if interval[0] == n and interval[1] == 'start':
					intervals_dict[interval[2]] = True
				else:
					intervals_deque.appendleft(interval)
					break
			self._cells[n] = len(intervals_dict)

	def GetMinSum(self):
		self._Process()
		w_end = self._H - 1
		min_sum = self._N * self._N
		w_sum = min_sum
		while w_end < self._N:
			w_start = w_end - self._H + 1
			if w_start == 0:
				w_sum = 0
				while w_start <= w_end:
					w_sum += self._GetHorizontalSum(w_start)
					w_start += 1
			else:
				w_sum += self._GetHorizontalSum(w_end) - self._GetHorizontalSum(w_start - 1)
			min_sum = min(w_sum, min_sum)
			w_end += 1
		return min_sum

def main():
	T = int(input())
	results = []
	for t in range(T):
		N_H = input().split()
		N = int(N_H[0])
		H = int(N_H[1])
		way_out = WayOut(N, H)
		for i in range(N):
			cells = input().split()
			cell_start = int(cells[0])
			cell_end = int(cells[1])
			way_out._AddCell(i, cell_start, cell_end)
		results.append(way_out.GetMinSum())
	for t in range(T):
		print(results[t])
main()


t = int(input())
while t > 0:
	(n, h) = [int(x) for x in input().split()]
	h3 = n * h
	r = [0] * 1000002
	for i in range(n):
		(a, b) = [int(x) for x in input().split()]
		r[a] = r[a] + 1
		r[b + 1] = r[b + 1] - 1
	max = r[0]
	for i in range(1, n):
		r[i] = r[i - 1] + r[i]
		if i < h:
			max = max + r[i]
	h1 = max
	for i in range(1, n - h + 1):
		h1 = h1 - r[i - 1] + r[i + h - 1]
		if h1 == h3:
			max = h1
			break
		if h1 > max:
			max = h1
	print(h3 - max)
	t = t - 1


def solve(size, tractor, columns):
	starts = {ix: 0 for ix in range(size)}
	stops = {ix: 0 for ix in range(size)}
	for (start, stop) in columns:
		starts[start] += 1
		stops[stop] += 1
	holes = []
	open_columns = 0
	for ix in range(size):
		open_columns += starts[ix]
		holes.append(open_columns)
		open_columns -= stops[ix]
	first_option = sum(holes[:tractor])
	options = [first_option]
	previous_option = first_option
	for ix in range(size - tractor):
		new_option = previous_option - holes[ix] + holes[ix + tractor]
		options.append(new_option)
		previous_option = new_option
	return size * tractor - max(options)
for _ in range(int(input())):
	(size, tractor) = [int(x) for x in input().strip().split()]
	sequence = []
	for _ in range(size):
		(start, stop) = [int(x) for x in input().strip().split()]
		sequence.append((start, stop))
	print(solve(size, tractor, sequence))


a = int(input())
while a > 0:
	a -= 1
	b = input()
	(n, h) = [int(n) for n in b.split()]
	A = [0] * (n + 2)
	B = [0] * (n + 2)
	for i in range(n):
		b = input()
		(q1, q2) = [int(n) for n in b.split()]
		A[q1] += -1
		A[q2 + 1] += 1
	t = 0
	for i in range(n):
		t += A[i]
		B[i] = t + n
	l = 0
	for i in range(h):
		l += B[i]
	l1 = 0
	l1 = l
	for i in range(1, n - h + 1):
		l1 = l1 - B[i - 1] + B[i + h - 1]
		l = min(l1, l)
	print(l)


import sys
t = int(sys.stdin.readline())
ans = [0] * t
for x in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	blanks = [0] * n
	num_starts = [0] * n
	num_ends = [0] * n
	for i in range(n):
		(s, e) = map(int, sys.stdin.readline().split())
		num_starts[s] += 1
		num_ends[e] += 1
	blanks[0] = num_starts[0]
	for i in range(1, n):
		blanks[i] = blanks[i - 1] + num_starts[i] - num_ends[i - 1]
	max_blanks = sum(blanks[:m])
	current_blanks = max_blanks
	for i in range(m, n, 1):
		current_blanks += blanks[i] - blanks[i - m]
		if current_blanks > max_blanks:
			max_blanks = current_blanks
	ans[x] = n * m - max_blanks
for _t in range(t):
	print(ans[_t])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	d = [0] * (n + 2)
	for j in range(n):
		(a, b) = map(int, input().split())
		d[a + 1] -= 1
		d[b + 2] += 1
	for x in range(1, n + 1):
		d[x] += d[x - 1]
	m = n * k
	y = n * k
	s = sum(d[1:1 + k])
	y = min(s + m, y)
	for z in range(2, n - k + 2):
		s = s - d[z - 1] + d[z + k - 1]
		y = min(s + m, y)
	print(y)


t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	L = [0] * (n + 2)
	for i in range(n):
		(a, b) = map(int, input().split())
		L[a + 1] -= 1
		L[b + 2] += 1
	L[0] = n
	for i in range(n):
		L[i + 1] += L[i]
	ans = s = sum(L[1:h + 1])
	for i in range(h + 1, n + 1):
		s += L[i] - L[i - h]
		ans = min(ans, s)
	print(ans)


import sys
input = sys.stdin.readline
tests = int(input())
for t in range(tests):
	(n, h) = [int(i) for i in input().split()]
	starts = []
	ends = []
	for i in range(n):
		l = [int(j) for j in input().split()]
		starts.append(l[0])
		ends.append(l[1])
	starts.sort()
	ends.sort()
	blocks = n
	a = []
	startpos = 0
	endpos = 0
	for i in range(n):
		while startpos < n and starts[startpos] == i:
			blocks -= 1
			startpos += 1
		while endpos < n and ends[endpos] == i - 1:
			blocks += 1
			endpos += 1
		a.append(blocks)
	toclear = sum(a[0:h])
	best = toclear
	for i in range(h, n):
		toclear += a[i]
		toclear -= a[i - h]
		best = min(toclear, best)
	print(best)


def read_line_as_integer_tuple():
	return tuple(map(int, input().split()))
t = int(input())
for i in range(t):
	(n, h) = read_line_as_integer_tuple()
	gaps = [0] * (n + 1)
	for j in range(n):
		(a, b) = read_line_as_integer_tuple()
		gaps[a] += 1
		gaps[b + 1] -= 1
	s = gaps[0]
	for j in range(1, h):
		gaps[j] += gaps[j - 1]
		s += gaps[j]
	m = s
	for j in range(h, n + 1):
		gaps[j] += gaps[j - 1]
		s = s - gaps[j - h] + gaps[j]
		m = max(m, s)
	print(n * h - m)


import math
import bisect

def inn():
	return int(input())

def inl():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
INF = inf = 10 ** 18 + 5
for t in range(int(input())):
	(n, h) = inl()
	gap = []
	for i in range(n):
		gap.append(inl())
	start = [0] * n
	end = [0] * n
	row = [0] * n
	for i in range(n):
		start[gap[i][0]] += 1
		end[gap[i][1]] += 1
	row[0] = start[0]
	for i in range(1, n):
		row[i] = row[i - 1] + start[i] - end[i - 1]
	presum = [0] * n
	presum[0] = row[0]
	for i in range(1, n):
		presum[i] = presum[i - 1] + row[i]
	ans = presum[h - 1]
	for i in range(h, n):
		ans = max(ans, presum[i] - presum[i - h])
	print(n * h - ans)


t = int(input())
for i in range(t):
	(n, h) = map(int, input().strip().split())
	a = [0] * (n + 1)
	for j in range(n):
		(start, end) = map(int, input().strip().split())
		a[start + 1] += 1
		if end + 1 != n:
			a[end + 2] -= 1
	dummy = 0
	for j in range(1, n + 1):
		dummy += a[j]
		a[j] = n - dummy
	mini = n * h
	for j in range(1, n - h + 2):
		if j == 1:
			sumi = sum(a[j:j + h])
		else:
			sumi += a[j + h - 1] - a[j - 1]
		if mini > sumi:
			mini = sumi
	print(mini)


for T in range(int(input())):
	(N, H) = [int(s) for s in input().strip().split(' ')]
	a = [0 for i in range(N + 1)]
	for i in range(N):
		(x, y) = [int(s) for s in input().strip().split(' ')]
		a[x] += 1
		a[y + 1] -= 1
	for i in range(1, N + 1):
		a[i] += a[i - 1]
	total = 0
	for i in range(H):
		total += a[i]
	mx = total
	for i in range(H, N):
		total += a[i] - a[i - H]
		if total > mx:
			mx = total
	print(N * H - mx)


for t in range(int(input())):
	(n, h) = map(int, input().split())
	arr = []
	(start, end) = ([0] * n, [0] * n)
	for i in range(n):
		(x, y) = map(int, input().split())
		start[x] += 1
		end[y] += 1
	sand = [0] * n
	sand[0] = n - start[0]
	for i in range(1, n):
		sand[i] = sand[i - 1] - start[i] + end[i - 1]
	_min = 0
	for i in range(0, h):
		_min += sand[i]
	newSum = _min
	for i in range(h, n):
		newSum = newSum + sand[i] - sand[i - h]
		if newSum < _min:
			_min = newSum
	print(_min)


t = int(input())
for _ in range(t):
	(n, h) = list(map(int, input().split()))
	wall = [n for i in range(n)]
	ops = [0 for i in range(n)]
	cls = [0 for i in range(n)]
	for i in range(n):
		(li, hi) = list(map(int, input().split()))
		ops[li] += 1
		cls[hi] += 1
	smash = 0
	for i in range(n):
		smash += ops[i]
		wall[i] -= smash
		smash -= cls[i]
	energy = 0
	for i in range(h):
		energy += wall[i]
	minenergy = energy
	for i in range(h, n):
		energy += wall[i]
		energy -= wall[i - h]
		minenergy = min(energy, minenergy)
	print(minenergy)


for tests in range(int(input())):
	[N, H] = [int(i) for i in input().split()]
	count = [0 for i in range(1 + N)]
	for i in range(N):
		[li, hi] = [int(i) for i in input().split()]
		count[li] += 1
		count[hi + 1] -= 1
	s = 0
	for i in range(N):
		s += count[i]
		count[i] = s
	current = sum(count[:H])
	maxi = current
	for i in range(0, N - H):
		current += count[i + H] - count[i]
		maxi = max(maxi, current)
	print(N * H - maxi)


for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	h = temp[1]
	energy = []
	energy.append(n)
	for i in range(n):
		energy.append(0)
	for q in range(n):
		temp = list(map(int, input().split()))
		lb = temp[0]
		ub = temp[1]
		energy[lb] -= 1
		if ub + 1 < n:
			energy[ub + 1] += 1
	dp = []
	s = energy[0]
	dp.append(s)
	for i in range(1, n):
		s += energy[i]
		dp.append(s)
	i = 0
	s = 0
	while i < n and i < h:
		s += dp[i]
		i += 1
	ans = s
	while i < n:
		s -= dp[i - h]
		s += dp[i]
		if s < ans:
			ans = s
		i += 1
	print(ans)