All Submissions


Problem Statement

Bugs Bunny is on straight road which is infinitely long. The points on this road are numbered as ...,-4,-3,-2,-1,0,1,2,3,4,5,.. from south to north. Bugs Bunny is at the point 0 now and he is going to meet Daffy Duck who is at the point 1,000,000,001. Bugs Bunny only moves by hopping and he can perform two types of hop: big hop and small hop. If Bugs Bunny is at the point x,
  • By making a small hop, he can either move to (x+2) or (x-2)
  • By making a big hop, he can either move to (x+bigHop) or (x-bigHop)

Unfortunately Elmer Fudd, the archenemy of Bugs Bunny wants to trap Bugs and puts traps on the road. Bugs Bunny can never get out if he lands on a point containing a trap. You are given an array of integers traps[] having N * 2 elements. For each i (0 <= i < N) , all the points between traps[2 * i] and traps[2 * i + 1], inclusive, contain traps.

Bugs Bunny prefers to do small hops because it is easier and faster. Find the minimum number of big hops required to reach Daffy Duck.

Input Specification

The first line of input contains T, the number of test cases.

For each test case, the first line contains N. The second line contains (2*N) elements of traps[]. The last line contains an integer giving the value of bigHop.

Each testcase is separated by a blank line.

Output Specification

For each test case, output the minimum number of big hops required to reach Daffy Duck. If it's not possible to reach Daffy Duck, the output should be -1.

Constraints
  • 1 <= N <= 25
  • 1 <= trap[i] <= 1,000,000,000 for all i
  • trap[] is in strictly increasing order
  • 3 <= bigHop <= 1,000,000,000

Sample Input

5
1
1 2
3

1
1 2
4

1
2 3
3

2
4 5 6 10
7

9
101557142 210995878 245344736 257981537 314968406 363946193 424279117 435779304 441820162 498117144 507089544 553226276 612496883 675096026 730940846 819627580 861535050 862716271
123866101


Sample Output

1
-1
3
-1
9

Explanation

Case #1:
trap[]={1, 2}
bigHop=3
Path: 0,3,5,7,9,.....999999997,999999999,1000000001
No. of big hops made is 1

Case #2: Bugs Bunny can never reach any odd-numbered point.

Case #3:
trap[]={2,3}
bigHop=3
Path: 0, -2, 1, 4, 7, 9, 11,....999999997,999999999, 1000000001
No. of big hops made is 3

Problem Setter : Rohan Laishram

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0