Read problem statements in [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is playing a noob version of the game Flappy Bird with the following rules:
The bird starts at a height $H$ at $x = 0$.
There are $N$ obstacles (numbered $1$ through $N$). For each valid $i$, the $i$-th obstacle is at a position $x_{i}$ and it has a height $h_{i}$.
For each integer $i$ ($0 ≤ i < x_{N}$), Chef has the option to click once when the bird is at $x = i$. Let's denote the bird's height ($y$-coordinate) at that point by $j$. If he clicks, the bird moves to $x = i+1$ and $y = j+1$. Otherwise, the bird moves to $x = i+1$ and $y = j-1$.
There is no ceiling and all the obstacles extend upwards from the bottom and not the other way around.
For each valid $i$, the bird crosses the $i$-th obstacle successfully if the bird's height at $x = x_{i}$ is strictly greater than $h_{i}$.
At any point before $x = x_{N}$, the bird's height should remain non-negative, otherwise it will drown.
If the bird crosses the $N$-th obstacle successfully, Chef wins the game.

Can you tell Chef if he can win the game (get the bird to cross all the obstacles) and the minimum number of clicks required to win in such a case?

------  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 $H$.
The second line contains $N$ space-separated integers $x_{1}, x_{2}, \ldots, x_{N}$.
The third line contains $N$ space-separated integers $h_{1}, h_{2}, \ldots, h_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum number of clicks required to cross all the obstacles successfully, or $-1$ if it is impossible to cross all the obstacles.

------  Constraints ------
$1 ≤ T ≤ 3 \cdot 10^{4}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ H ≤ 10^{9}$
$1 ≤ x_{1} < x_{2} < \ldots < x_{N} ≤ 10^{9}$
$1 ≤ h_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------  Example Input ------

3
1 0
2
1
2 1
1 3
1 1
5 10
1 2 3 4 5
10 11 12 13 15

------  Example Output ------

2
2
-1
	
------  Explanation ------
Example case 2: The figure below shows one possible way to successfully cross all the obstacles using the minimum number of clicks.

Example case 3: It is clear that even by clicking all the time, it is impossible to cross the last obstacle.

Difficulty: VERY_HARD
Tags: Greedy algorithms

Sorting

Complete search
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	x = list(map(int, input().split()))
	h1 = list(map(int, input().split()))
	for j in range(n):
		h1[j] = h1[j] - h
	c = 0
	for k in range(n):
		if x[k] <= h1[k]:
			print(-1)
			c = 1
			break
	ans = 0
	for z in range(n):
		if (h1[z] + x[z] + 2) / 2 > ans:
			ans = (h1[z] + x[z] + 2) / 2
	if c == 0:
		print(int(ans))


T = int(input())
for i in range(T):
	(N, H) = input().split()
	N = int(N)
	H = int(H)
	X = list(map(int, input().split()))
	Heights = list(map(int, input().split()))
	for i in range(N):
		Heights[i] = Heights[i] - H
	c = 0
	for i in range(N):
		if X[i] <= Heights[i]:
			print(-1)
			c = 1
			break
	ans = 0
	for i in range(N):
		if (Heights[i] + X[i] + 2) / 2 > ans:
			ans = (Heights[i] + X[i] + 2) / 2
	if c == 0:
		print(int(ans))


n_testcase = int(input())
for testcase in range(n_testcase):
	(n, initial_height) = (int(x) for x in input().split())
	obstacle_positions = [int(x) for x in input().split()]
	obstacle_heights = [int(x) for x in input().split()]
	obstacles = list(zip(obstacle_positions, obstacle_heights))
	impossible = any((obstacle_height - initial_height >= obstacle_position for (obstacle_position, obstacle_height) in obstacles))
	if impossible:
		print(-1)
		continue
	left = max((max(obstacle_positions) - initial_height + 1) // 2, 0)
	right = 10 ** 9
	while left < right:
		mid = (left + right) // 2
		for (obstacle_position, obstacle_height) in obstacles:
			count_up = min(mid, obstacle_position)
			count_down = obstacle_position - count_up
			if initial_height + count_up - count_down <= obstacle_height:
				left = mid + 1
				break
		else:
			right = mid
	print(right)


def check(k, x, h, H):
	for i in range(len(x)):
		if x[i] <= k and H + x[i] <= h[i]:
			return False
		if x[i] > k and H + k - (x[i] - k) <= h[i]:
			return False
	return True
for _ in range(int(input())):
	(N, H) = map(int, input().split())
	x = list(map(int, input().split()))
	h = list(map(int, input().split()))
	(l, r) = (0, 10 ** 9)
	ans = -1
	while l <= r:
		mid = (l + r) // 2
		if check(mid, x, h, H):
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	print(ans)


for _ in range(int(input())):
	(n, H) = map(int, input().rstrip().split())
	x = list(map(int, input().rstrip().split()))
	h = list(map(int, input().rstrip().split()))
	p = list()
	for i in range(n):
		p.append((x[i], h[i] - H))
	flag = True
	clicks = 0
	for (x, h) in p:
		if x <= h:
			flag = False
			break
		clicks = max((x + h + 2) // 2, clicks)
	if flag:
		print(clicks)
	else:
		print(-1)


import math
t = int(input())
for _ in range(t):
	(n, H) = map(int, input().split())
	positions = list(map(int, input().split()))
	heights = list(map(int, input().split()))
	ans = 0
	p = 0
	d = positions[0] - 0
	h = heights[0] + 1 - H
	x = max(0, math.ceil((d + h) / 2))
	prev_h = H + x - (d - x)
	alone = d - x
	if x > d:
		p = 1
	else:
		ans = ans + x
		for i in range(1, n):
			d = positions[i] - positions[i - 1]
			h = heights[i] + 1 - prev_h
			x = max(0, math.ceil((d + h) / 2))
			if x > d:
				if alone >= math.ceil((h - d) / 2):
					prev_h = prev_h + d + 2 * math.ceil((h - d) / 2)
					alone = alone - math.ceil((h - d) / 2)
					ans = ans + d + math.ceil((h - d) / 2)
				else:
					p = 1
					break
			else:
				ans = ans + x
				prev_h = prev_h + x - (d - x)
				alone = alone + d - x
	if p == 1:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	(N, H) = map(int, input().split())
	l = []
	for i in input().split():
		x = int(i)
		l.append(x)
	h = []
	for i in input().split():
		x = int(i)
		h.append(x - H)
	flag = True
	ans = 0
	for (a, b) in zip(l, h):
		if a <= b:
			flag = False
			break
		ans = max(ans, (a + b + 2) // 2)
	print(ans if flag else -1)


t = int(input())
for _ in range(t):
	(n, H) = map(int, input().split())
	x = list(map(int, input().split()))
	h = list(map(int, input().split()))
	res = []
	for i in range(len(h)):
		s = h[i] - H
		res.append(s)
	result = 0
	flag = 0
	for i in range(len(res)):
		if x[i] > res[i]:
			result = max(result, (x[i] + res[i] + 2) // 2)
		else:
			flag = 1
			break
	if flag == 0:
		print(result)
	else:
		print('-1')


maxx = 1000000009

def check(k, x, h, n):
	for i in range(n):
		if x[i] <= k:
			if h[i] >= H + x[i]:
				return False
		elif h[i] >= H + k - (x[i] - k):
			return False
	return True
for __ in range(int(input())):
	(n, H) = map(int, input().split())
	x = list(map(int, input().split()))
	h = list(map(int, input().split()))
	low = 0
	high = maxx
	ans = -1
	while low <= high:
		mid = low + (high - low) // 2
		if check(mid, x, h, n):
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)


def check(x):
	for i in range(n):
		if X[i] <= x:
			if H[i] >= X[i]:
				return False
		elif H[i] >= x - (X[i] - x):
			return False
	return True
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	X = list(map(int, input().split()))
	H = list(map(int, input().split()))
	for i in range(n):
		H[i] -= h
	s = 0
	e = 2000000000
	while s < e:
		mid = (s + e) // 2
		if check(mid) == False:
			s = mid + 1
		else:
			e = mid
	if s > 1000000010:
		s = -1
	print(s)


def check(obs_pos, obs_h, h, clicks):
	for i in range(len(obs_pos)):
		if i == 0:
			if clicks <= obs_pos[0]:
				h += clicks
				h -= obs_pos[0] - clicks
				clicks = 0
			else:
				h += obs_pos[0]
				clicks -= obs_pos[0]
		elif clicks <= obs_pos[i] - obs_pos[i - 1]:
			h += clicks
			h -= obs_pos[i] - obs_pos[i - 1] - clicks
			clicks = 0
		elif clicks > obs_pos[i] - obs_pos[i - 1]:
			h += obs_pos[i] - obs_pos[i - 1]
			clicks -= obs_pos[i] - obs_pos[i - 1]
		if h <= obs_h[i]:
			return False
	else:
		return True

def bsearch(obs_pos, obs_h, h):
	left = 0
	right = obs_pos[-1]
	ans = -1
	while left <= right:
		mid = left + (right - left) // 2
		if check(obs_pos, obs_h, h, mid):
			ans = mid
			right = mid - 1
		else:
			left = mid + 1
	return ans
for i in range(int(input())):
	(n, h) = map(int, input().split())
	obs_pos = [int(x) for x in input().split()]
	obs_h = [int(h) for h in input().split()]
	ans = bsearch(obs_pos, obs_h, h)
	print(ans)


for _ in range(int(input())):
	(n, h) = map(int, input().split())
	X = list(map(int, input().split()))
	H = list(map(int, input().split()))
	Y = []
	for i in range(n):
		x = X[i]
		reqh = H[i]
		if reqh >= h + x:
			print(-1)
			break
		else:
			Y.append(h + x - reqh - 1)
	else:
		c = 0
		m = Y[-1]
		for i in range(n - 1, -1, -1):
			m = min(m, Y[i])
			if m <= 1:
				break
			tick = X[i] - (X[i - 1] if i != 0 else 0)
			lw = min(m // 2, tick)
			c += lw
			m -= lw * 2
		print(X[-1] - c)