There is a building with 10^{9} floors labelled 1 to 10^{9} from the bottom to the top. N people would like to move up several floors in the building. Specifically, the i-th person wants to move from floor A_{i} to floor B_{i}, where A_{i} < B_{i}.

There are M elevators in the building. An elevator can hold any number of people. Initially, at the 0-th second, all elevators are at floor 1. 

An elevator takes 1 second to move up 1 floor but cannot move down any floors. On any floor, an elevator may stop so that people may enter or exit the elevator. Each person takes H seconds to enter or exit an elevator. Two or more people cannot enter or exit the same elevator at the same time; they must wait for their turn. 

A person can exit an elevator on any floor, not only floor B_{i}. In particular, a person can switch elevators by exiting on some floor and entering a different elevator on the same floor.

We say that the i-th person has reached the destination after taking H seconds to exit an elevator at floor B_{i}. 

Find the minimum time needed in seconds until all N people have reached their destinations if they enter and exit elevators optimally.

*Note: We would recommend Python users to use PYPY/PYPY3 instead of PYTHON/PYTHON3.*

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains three integers N, M and H — the number of people, the number of elevators and the time taken for a person to enter or exit an elevator.
- N lines follow. The i-th line contains two integers A_{i} and B_{i}, where the i-th person wants to move from floor A_{i} to floor B_{i}.

------ Output Format ------ 

For each test case, output a single integer on a new line, representing the minimum time needed until all N people have reached their destinations.

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

$1 ≤T ≤10^{5}$
$1 ≤N, M ≤3 \cdot 10^{5}$
$1 ≤H ≤10^{9}$
$1 ≤A_{i} < B_{i} ≤10^{9}$
- The sum of $N$ over all test cases will not exceed $3 \cdot 10^{5}$
- The sum of $M$ over all test cases will not exceed $3 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
5 3 2
12 24
2 3
5 6
3 8
5 11
1 20 23
20 23
6 3 998244353
3 9
3 9
3 9
3 9
3 9
3 9

----- Sample Output 1 ------ 
27
68
3992977420

----- explanation 1 ------ 
For the first test case, a possible sequence of events is given as follows for each elevator.

Elevator $1$:

- At the $0$-th second, elevator $1$ starts moving up from floor $1$.
- At the $2$-nd second, elevator $1$ stops at floor $3$. Person $4$ starts entering elevator $1$.
- At the $4$-th second, person $4$ finishes entering elevator $1$. Elevator $1$ continues moving up from floor $3$.
- At the $6$-th second, elevator $1$ stops at floor $5$. Person $4$ starts exiting elevator $1$.
- At the $8$-th second, person $4$ finishes exiting elevator $1$. Elevator $1$ continues moving up from floor $5$.

Elevator $2$:

- At the $0$-th second, elevator $2$ starts moving up from floor $1$.
- At the $1$-st second, elevator $2$ stops at floor $2$. Person $2$ starts entering elevator $2$.
- At the $3$-rd second, person $2$ finishes entering elevator $2$. Elevator $2$ continues moving up from floor $2$.
- At the $4$-th second, elevator $2$ stops at floor $3$. Person $2$ starts exiting elevator $2$.
- At the $6$-th second, person $2$ finishes exiting elevator $2$. Elevator $2$ continues moving up from floor $3$.
- At the $8$-th second, elevator $2$ stops at floor $5$. Person $4$ starts entering elevator $2$.
- At the $10$-th second, person $4$ finishes entering elevator $2$. Person $3$ starts entering elevator $2$.
- At the $12$-th second, person $3$ finishes entering elevator $2$. Person $5$ starts entering elevator $2$.
- At the $14$-th second, person $5$ finishes entering elevator $2$. Elevator $2$ continues moving up from floor $5$.
- At the $15$-th second, elevator $2$ stops at floor $6$. Person $3$ starts exiting elevator $2$.
- At the $17$-th second, person $3$ finishes exiting elevator $2$. Elevator $2$ continues moving up from floor $6$.
- At the $19$-th second, elevator $2$ stops at floor $8$. Person $4$ starts exiting elevator $2$.
- At the $21$-st second, person $4$ finishes exiting elevator $2$. Elevator $2$ continues moving up from floor $8$.
- At the $24$-th second, elevator $2$ stops at floor $11$. Person $5$ starts exiting elevator $2$.
- At the $26$-th second, person $5$ finishes exiting elevator $2$. Elevator $2$ continues moving up from floor $11$.

Elevator $3$:

- At the $0$-th second, elevator $3$ starts moving up from floor $1$.
- At the $11$-th second, elevator $3$ stops at floor $12$. Person $1$ starts entering elevator $3$.
- At the $13$-th second, person $1$ finishes entering elevator $3$. Elevator $3$ continues moving up from floor $12$.
- At the $25$-th second, elevator $3$ stops at floor $24$. Person $1$ starts exiting elevator $3$.
- At the $27$-th second, person $1$ finishes exiting elevator $3$. Elevator $3$ continues moving up from floor $24$.

All people reach their destinations by $27$ seconds. Notice that person $4$ switched elevators, which is allowed. It can be shown that there is no way for them to reach their destinations by $26$ seconds or fewer.

Source: codechef | Difficulty: VERY_HARD
Tags: Greedy algorithms

Sorting

Complete search


Solutions:
def sim(b, n, m, h, x):
	Need = 0
	Limit = b[0] - 1 + 2 * h
	if Limit > x:
		return False
	for i in range(1, n):
		if Limit + 2 * h <= x:
			Limit += 2 * h
		else:
			Limit = b[i] - 1 + 2 * h
			Need += 1
	return Need < m
for _ in range(int(input())):
	(n, m, h) = map(int, input().split())
	b = []
	for _ in range(n):
		(ai, bi) = map(int, input().split())
		b.append(bi)
	b.sort(reverse=True)
	(lo, hi) = (0, 10 ** 15)
	while lo < hi:
		mid = (lo + hi) // 2
		if sim(b, n, m, h, mid):
			hi = mid
		else:
			lo = mid + 1
	print(lo)


def simulate(b, n, m, h, x):
	need = 0
	limit = b[0] - 1 + 2 * a
	if limit > x:
		return False
	for i in range(1, n):
		if limit + 2 * a <= x:
			limit += 2 * a
		else:
			limit = b[i] - 1 + 2 * a
			need += 1
	return need < m
for _ in range(int(input())):
	(n, m, a) = map(int, input().split())
	b = []
	for _ in range(n):
		(ai, bi) = map(int, input().split())
		b.append(bi)
	b.sort(reverse=True)
	(lo, hi) = (0, 10 ** 15)
	while lo < hi:
		mid = (lo + hi) // 2
		if simulate(b, n, m, a, mid):
			hi = mid
		else:
			lo = mid + 1
	print(lo)


def simulate(a, no, m, h, p):
	need = 0
	limit = a[0] - 1 + 2 * h
	if limit > p:
		return False
	for i in range(1, no):
		if limit + 2 * h <= p:
			limit += 2 * h
		else:
			limit = a[i] - 1 + 2 * h
			need += 1
	return need < m
for _ in range(int(input())):
	(no, m, h) = map(int, input().split())
	a = []
	for _ in range(no):
		(ai, bi) = map(int, input().split())
		a.append(bi)
	a.sort(reverse=True)
	(low, high) = (0, 10 ** 15)
	while low < high:
		mid = (low + high) // 2
		if simulate(a, no, m, h, mid):
			high = mid
		else:
			low = mid + 1
	print(low)


for _ in range(int(input())):
	(n, m, h) = map(int, input().split())
	floors = []
	for i in range(n):
		(a, b) = map(int, input().split())
		floors.append((a, b))
	floors.sort(key=lambda x: x[1])
	(lo, hi) = (0, 10 ** 18)
	while lo < hi:
		mid = (lo + hi) // 2
		need = 0
		cur = mid + 1
		reach = True
		for (a, b) in floors:
			if cur + b + 2 * h <= mid:
				cur += 2 * h
			elif b + 2 * h > mid:
				reach = False
				break
			else:
				cur = 2 * h
				need += 1
		if reach == False or need > m:
			lo = mid + 1
		else:
			hi = mid
	print(lo - 1)


def funSim(b, n, m, h, x):
	nd = 0
	maap = b[0] - 1 + 2 * h
	if maap > x:
		return False
	for i in range(1, n):
		if maap + 2 * h <= x:
			maap += 2 * h
		else:
			maap = b[i] - 1 + 2 * h
			nd += 1
	return nd < m
for _ in range(int(input())):
	(n, m, h) = map(int, input().split())
	b = []
	for _ in range(n):
		(ai, bi) = map(int, input().split())
		b.append(bi)
	b.sort(reverse=True)
	(loww, highh) = (0, 10 ** 15)
	while loww < highh:
		mid = (loww + highh) // 2
		if funSim(b, n, m, h, mid):
			highh = mid
		else:
			loww = mid + 1
	print(loww)


def simulate(y, n1, m2, h, x1):
	need = 0
	limit = y[0] - 1 + 2 * h
	if limit > x1:
		return False
	for i in range(1, n1):
		if limit + 2 * h <= x1:
			limit += 2 * h
		else:
			limit = y[i] - 1 + 2 * h
			need += 1
	return need < m2
for _ in range(int(input())):
	(n1, m2, h) = map(int, input().split())
	y = []
	for _ in range(n1):
		(ai, yi) = map(int, input().split())
		y.append(yi)
	y.sort(reverse=True)
	(lower, higher) = (0, 20 ** 25)
	while lower < higher:
		mid = (lower + higher) // 2
		if simulate(y, n1, m2, h, mid):
			higher = mid
		else:
			lower = mid + 1
	print(lower)


def simulate(b, n1, m2, h, x1):
	need = 0
	limit = b[0] - 1 + 2 * h
	if limit > x1:
		return False
	for i in range(1, n1):
		if limit + 2 * h <= x1:
			limit += 2 * h
		else:
			limit = b[i] - 1 + 2 * h
			need += 1
	return need < m2
for _ in range(int(input())):
	(n1, m2, h) = map(int, input().split())
	b = []
	for _ in range(n1):
		(ai, bi) = map(int, input().split())
		b.append(bi)
	b.sort(reverse=True)
	(low, high) = (0, 20 ** 25)
	while low < high:
		mid = (low + high) // 2
		if simulate(b, n1, m2, h, mid):
			high = mid
		else:
			low = mid + 1
	print(low)


def is_ok(time, m, h, dests):
	i = 0
	j = 0
	while True:
		i += (time - dests[i]) // (2 * h)
		if i >= len(dests):
			return True
		j += 1
		if j >= m:
			return False
for _ in range(int(input())):
	(n, m, h) = (int(x) for x in input().split())
	assert n >= 1 and m >= 1 and (h >= 1)
	dests = []
	for __ in range(n):
		(a, b) = (int(x) for x in input().split())
		assert b > a and a >= 1
		dests.append(b - 1)
	dests.sort(reverse=True)
	min_time = max(dests) + 2 * h
	max_time = max(dests) + 2 * h * n
	while True:
		if min_time == max_time:
			break
		med_time = (min_time + max_time) // 2
		if is_ok(med_time, m, h, dests):
			max_time = med_time
		else:
			min_time = med_time + 1
	print(min_time)


for _ in range(int(input())):
	[n, m, h] = list(map(int, input().split()))
	arr = []
	for i in range(n):
		[a, b] = list(map(int, input().split()))
		arr.append(b)
	arr.sort()

	def solve(k):
		index = n - 1
		elevs = m
		time = arr[index] - 1
		while index >= 0 and elevs:
			while index >= 0 and time + 2 * h <= k:
				time += 2 * h
				index -= 1
			if index < 0:
				break
			elevs -= 1
			time = arr[index] - 1
		if index < 0:
			return 1
		return 0
	l = arr[-1] + 2 * h - 1
	r = arr[-1] + 2 * h * n - 1
	while l < r:
		mid = (l + r) // 2
		if solve(mid):
			r = mid
		else:
			l = mid + 1
	print(l)