Chef has a grid of size N \times M. 

In one move, Chef can move from his current cell to an adjacent cell. If the Chef is currently at (i, j) then, in one move, Chef can move to (i + 1, j), (i - 1, j), (i, j + 1) or (i, j - 1).

There are also K *special* cells in the grid. These special cells support a corner move as well. If the Chef is currently at a *special* cell (i, j) then, in one move, Chef can move to (i + 1, j + 1), (i - 1, j - 1), (i + 1, j - 1) or (i - 1, j + 1) in addition to the adjacent cells ((i + 1, j), (i - 1, j), (i, j + 1) or (i, j - 1)). 

Chef is not allowed to leave the grid at any moment. Determine the minimum number of moves Chef needs to go from (1, 1) to (N, M).

------ 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 space-separated integers N, M and K — the number of rows in the grid, the number of columns in the grid and the number of special cells.
- K lines follow. The i-th line of these K lines contains two space-separated integers X_{i} and Y_{i} such that (X_{i}, Y_{i}) is the i-th special cell.

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

For each test case, output the minimum number of moves required by the Chef to go to (N, M) from (1, 1).

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

$1 ≤ T ≤ 10^{4}$ 
$1 ≤ N, M ≤ 10^{9}$ 
$0 ≤ K ≤ 2 \cdot 10^{5}$ 
$1 ≤ X_{i} ≤ N$, $1 ≤ Y_{i} ≤ M$ 
- All $(X_{i}, Y_{i})$ are pairwise distinct.
- Sum of $K$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
3 3 0
3 3 2
2 2
2 3

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

----- explanation 1 ------ 
Test Case 1: There is no special cell in this case. One of the optimal ways is: $(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3)$. Therefore a total of $4$ moves is required.

Test Case 2: There are $2$ special cells in this case. One of the optimal ways is: $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (3,3)$. Therefore a total of $3$ moves is required.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
import bisect

def LII():
	return [int(x) for x in input().split()]

def longest_incr_length(s):
	vec_last = []
	for x in s:
		i = bisect.bisect_left(vec_last, x)
		if i != len(vec_last):
			vec_last[i] = x
		else:
			vec_last.append(x)
	return len(vec_last)
for _ in range(int(input())):
	(n, m, k) = LII()
	specials = []
	for __ in range(k):
		(sx, sy) = LII()
		if sx != n and sy != m:
			specials.append((sx, sy))
	specials.sort(key=lambda p: (p[0], -p[1]))
	max_spec = longest_incr_length([y for (x, y) in specials])
	print(m + n - 2 - max_spec)


from sys import stdin
input = stdin.readline

def lis(nums, cmp=lambda x, y: x < y):
	P = [0] * len(nums)
	M = [0] * (len(nums) + 1)
	L = 0
	for i in range(len(nums)):
		(lo, hi) = (1, L)
		while lo <= hi:
			mid = (lo + hi) // 2
			if cmp(nums[M[mid]], nums[i]):
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		L = max(L, newL)
	S = [0] * L
	k = M[L]
	for i in range(L - 1, -1, -1):
		(S[i], k) = (nums[k], P[k])
	return S

def solve(N, M, specials):
	specials = [(X, -Y) for (X, Y) in specials]
	specials = sorted(specials)
	specials = [-Y for (X, Y) in specials]
	return N + M - 2 - len(lis(specials))
T = int(input().strip())
for problem in range(1, T + 1):
	(N, M, K) = [int(x) for x in input().strip().split()]
	specials = set()
	for i in range(K):
		(X, Y) = [int(x) for x in input().strip().split()]
		if X < N and Y < M:
			specials.add((X, Y))
	print(solve(N, M, specials))


from bisect import bisect_left

def lis(a):
	s = []
	for el in a:
		if not s:
			s.append(el)
		else:
			ind = bisect_left(s, el)
			if ind == len(s):
				s.append(el)
			else:
				s[ind] = el
	return len(s)
for _ in range(int(input())):
	(m, n, q) = map(int, input().split())
	if q == 0:
		print(m - 1 + n - 1)
	else:
		ans = m - 1 + n - 1
		points = []
		for _ in range(q):
			points.append(list(map(int, input().split())))
		points.sort(key=lambda x: (x[0], -x[1]))
		t = [b for (a, b) in points if a < m and b < n]
		print(n + m - 2 - lis(t))


import bisect

def solve():
	(n, m, k) = map(int, input().split())
	tiles = []
	for _ in range(k):
		(l, w) = map(int, input().split())
		if l == n or w == m:
			k -= 1
		else:
			tiles.append((l, w))
	tiles.sort(key=lambda x: (x[0], -x[1]))
	lis = []
	for (l, w) in tiles:
		pos = bisect.bisect_left(lis, w)
		if pos == len(lis):
			lis.append(w)
		else:
			lis[pos] = w
	print(n + m - 2 - len(lis))
t = int(input())
for _ in range(t):
	solve()


def lis(nums, cmp=lambda x, y: x < y):
	P = [0] * len(nums)
	M = [0] * (len(nums) + 1)
	L = 0
	for i in range(len(nums)):
		(lo, hi) = (1, L)
		while lo <= hi:
			mid = (lo + hi) // 2
			if cmp(nums[M[mid]], nums[i]):
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		L = max(L, newL)
	S = [0] * L
	k = M[L]
	for i in range(L - 1, -1, -1):
		(S[i], k) = (nums[k], P[k])
	return S
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	cells = []
	for i in range(k):
		(x, y) = map(int, input().split())
		if x < n and y < m:
			cells.append([x, -y])
	cells.sort()
	vals = []
	for (x, y) in cells:
		vals.append(-y)
	print(n - 1 + m - 1 - len(lis(vals)))


for _ in range(int(input())):
	[n, m, k] = list(map(int, input().split()))
	tot = (m - 1) * (n - 1)
	arr = []
	for i in range(k):
		[a, b] = list(map(int, input().split()))
		if a < n and b < m:
			arr.append((a, b))
	arr.sort(key=lambda x: (x[0], -1 * x[1]))
	import bisect
	x = []
	for i in arr:
		k = len(x)
		temp = bisect.bisect_left(x, i[1])
		if temp == k:
			x.append(i[1])
		else:
			x[temp] = i[1]
	print(m + n - 2 - len(x))