This page is still under construction.

Parts of this page are still being built. What you see may change.

Toy Car Race

Interview

Time limit1sMemory limit256 MB

Summary
Find the smallest booster distance Z (at most Y, whole meters per second for one second) so your car finishes the X-meter race strictly faster than every other car.
Level

Medium5 of 10

Topics
Math, Binary search, Implementation, Greedy
Solved
No attempts yet

Problem

N participants, including you, each race with their own toy car. The track is X meters long.

The participants are numbered 1 through N, and your number is N.

The normal speed of participant i's car is V[i] m/s. Every participant's car except yours moves from the start to the finish at a constant speed.

Your toy car has a special booster, so you can set it to move at Z m/s for the first 1 second. The rest of the track is covered at the constant speed V[N] m/s.

Before the race starts you may choose an integer Z, and this value must not exceed the booster speed limit Y m/s (Z ≤ Y).

You want to win this race outright. Using the booster too much could arouse suspicion, so you want the smallest Z that lets you win outright.

For example, let N = 3, X = 12, Y = 11, and V = [3, 2, 1].

  • Participant 1's car moves at a constant 3 m/s and finishes the race in 4 seconds.

  • Participant 2's car moves at a constant 2 m/s and finishes the race in 6 seconds.

  • For you, participant 3, there are several possibilities.

    • Without the booster, you move at a constant 1 m/s and finish the race in 12 seconds.
    • With the booster at its maximum (Z = Y), you cover 11 m in the first second, drive the remaining 1 m for 1 second, and finish in 2 seconds, winning outright.
    • Using the booster a little less, so that Z = 10 meters in 1 second, you cover the remaining 2 m at your normal speed, for 3 seconds in total, and win outright.
    • Using a little less still, so that Z = 9 meters in 1 second, you cover the remaining 3 m at your normal speed, for 4 seconds in total, the same time as participant 1 (a tie for first).

In this example you must cover at least 10 meters with the booster to win outright, so the answer is 10.

Given N, X, Y, and the speeds V of the toy cars, write a program that finds the minimum distance you must cover with the booster to win outright.

Input

The first line gives the number of test cases T.

The first line of each test case gives N, X, and Y, separated by spaces.

The second line gives N integers separated by spaces, the speeds V[i] of the toy cars.

Output

For each test case, print the minimum distance you must cover with the booster to win outright.

If you can win outright without using the booster, print 0.

If you cannot win outright even with the booster at its maximum, print -1.

Constraints

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 1,000
  • 1 ≤ Y ≤ X ≤ 1,000,000
  • 1 ≤ V[i] ≤ 1,000,000

Examples1

  1. Example 1

    Input
    5
3 12 11
3 2 1
3 12 9
3 2 1
3 12 10
3 4 5
3 80 80
80 60 70
3 80 80
70 50 60
    Expected output
    10
-1
0
-1
72