장난감 경주

당신을 포함한 N명의 참가자가 각자 자신의 장난감 자동차로 경주를 한다. 트랙의 길이는 X 미터이다.

참가자에게는 1번부터 N번까지 번호가 붙어 있고, 당신의 번호는 N번이다.

i번 참가자의 자동차가 평소에 내는 속도는 V[i] m/s이며, 당신을 제외한 모든 참가자의 자동차는 출발점에서 도착점까지 항상 일정한 속도로 움직인다.

당신의 장난감 자동차에는 특수 부스터가 있어서, 처음 1초 동안 Z m/s로 움직이도록 설정할 수 있다. 트랙의 나머지 거리는 V[N] m/s의 일정한 속도로 움직인다.

경주를 시작하기 전에 정수 Z를 고를 수 있고, 이 값은 부스터 속도 한계치 Y m/s 이하여야 한다 (Z ≤ Y).

당신은 이 경주에서 단독 1등을 하고 싶다. 부스터를 지나치게 사용하면 의심을 살 수 있으므로, 단독 우승이 가능하도록 하는 최소의 Z를 구하려 한다.

예를 들어 N = 3, X = 12, Y = 11이고 V = [3, 2, 1]이라 하자.

• 1번 참가자의 자동차는 3 m/s의 일정한 속도로 움직여 4초 만에 경주를 마친다.

• 2번 참가자의 자동차는 2 m/s의 일정한 속도로 움직여 6초 만에 경주를 마친다.

• 3번 참가자인 당신에게는 여러 가지 가능성이 있다.

  • 부스터를 사용하지 않으면 1 m/s의 일정한 속도로 움직여 12초 만에 경주를 마친다.
  • 부스터를 최대치로 사용하면 (Z = Y) 처음 1초 동안 11m를 이동하고, 남은 1m를 1초 동안 주행해서 2초 만에 경주를 마치며 단독 우승할 수 있다.
  • 부스터를 조금 덜 사용해 Z = 10미터를 1초 만에 이동하면, 남은 2m는 원래 속도로 이동해 총 3초가 걸리고 단독 우승할 수 있다.
  • 그보다 조금 덜 사용해 Z = 9미터를 1초 만에 이동하면, 남은 3m는 원래 속도로 이동해 총 4초가 걸리고 1번 자동차와 같은 시간이 걸린다 (공동 우승).

위 예제에서는 단독 우승을 위해 최소 10미터를 부스터로 이동해야 하므로 답은 10이다.

N, X, Y와 각 장난감 자동차의 속도 V가 주어졌을 때, 단독 우승을 위해 부스터로 이동해야 하는 최소 거리를 구하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에 N, X, Y가 공백으로 구분되어 주어진다.

둘째 줄에 N개의 정수가 공백으로 구분되어 주어지는데, 이는 각 장난감 자동차의 속도 V[i]를 나타낸다.

각 테스트 케이스에 대해 단독 우승을 위해 부스터로 이동해야 하는 최소 거리를 출력한다.

부스터를 쓰지 않고도 단독 우승이 가능하면 0을 출력한다.

부스터를 최대치로 사용하고도 단독 우승이 불가능하면 -1을 출력한다.

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