Flappy Bird Codechef Solution

by

Flappy Bird Solution Problem Code: FLAPPYBD

Chef is playing a noob version of the game Flappy Bird with the following rules:

  • The bird starts at a height HH at x=0x=0.
  • There are NN obstacles (numbered 11 through NN). For each valid ii, the ii-th obstacle is at a position xixi and it has a height hihi.
  • For each integer ii (0≤i<xN0≤i<xN), Chef has the option to click once when the bird is at x=ix=i. Let’s denote the bird’s height (yy-coordinate) at that point by jj. If he clicks, the bird moves to x=i+1x=i+1 and y=j+1y=j+1. Otherwise, the bird moves to x=i+1x=i+1 and y=j−1y=j−1.
  • There is no ceiling and all the obstacles extend upwards from the bottom and not the other way around.
  • For each valid ii, the bird crosses the ii-th obstacle successfully if the bird’s height at x=xix=xi is strictly greater than hihi.
  • At any point before x=xNx=xN, the bird’s height should remain non-negative, otherwise it will drown.
  • If the bird crosses the NN-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 TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers NN and HH.
  • The second line contains NN space-separated integers x1,x2,…,xNx1,x2,…,xN.
  • The third line contains NN space-separated integers h1,h2,…,hNh1,h2,…,hN.

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−1 if it is impossible to cross all the obstacles.

Constraints

  • 1≤T≤3⋅1041≤T≤3⋅104
  • 1≤N≤1051≤N≤105
  • 0≤H≤1090≤H≤109
  • 1≤x1<x2<…<xN≤1091≤x1<x2<…<xN≤109
  • 1≤hi≤1091≤hi≤109 for each valid ii
  • the sum of NN over all test cases does not exceed 5⋅1055⋅105

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.
Flappy Bird Codechef Solution
   
Example case 3: It is clear that even by clicking all the time, it is impossible to cross the last obstacle.
Flappy Bird Codechef Solution
   
Weekly Contest 247
Biweekly Contest 55
June Long Challenge 2021 Solutions
March Long Challenge 2021 Solutions
April Long Challenge 2021 Solutions
Codechef Long Challenge Solutions
February Long Challenge 2021
January Long Challenge 2021
November Challenge 2020 SOLUTION CodeChef
October Lunchtime 2020 CodeChef SOLUTIONS
Related :
Related :
Leave a Comment 



 
four × three =