마리오 카트

마리오 게임의 새 버전이 나왔다. 이번에는 카트 레이싱이다. 각 레벨을 가장 적은 이동 횟수로 끝내는 전략을 찾는 프로그램을 작성한다.

레벨의 트랙은 무한히 뻗은 직선이고, 트랙 위의 몇 지점에 정류장이 있다. 정류장의 위치는 정수다. 위치가 가장 작은 정류장에서 출발해 위치가 가장 큰 정류장까지 최소 이동 횟수로 가야 한다.

부스트 코인이 충분하다면 두 정류장 사이를 한 번에 이동할 수 있다. 바로 옆 정류장이 아닌 곳으로 건너뛰어도 되고, 위치가 더 작은 정류장으로 되돌아가도 된다. 레벨마다 쓸 수 있는 부스트 코인이 주어지고, 코인마다 비용과 추진력이 정해져 있다. 한 번 이동할 때 코인을 임의의 부분집합으로 고를 수 있지만, 한 번의 이동에서 같은 코인을 두 번 쓸 수는 없다. 코인은 없어지지 않으므로 같은 레벨의 다른 이동에서 다시 쓸 수 있다.

한 번 이동하려면 코인의 부분집합을 하나 골라야 한다. 고른 코인의 비용 합은 $L$ 이하여야 하고, 추진력 합은 출발 정류장과 도착 정류장의 위치 차이의 절댓값과 정확히 같아야 한다. 이런 부분집합이 없으면 두 정류장 사이를 직접 이동할 수 없다.

여러 레벨의 설정이 주어진다. 각 레벨을 끝내는 최소 이동 횟수를 구하거나, 끝낼 수 없다고 판정하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫째 줄에는 정류장의 개수 $N$, 부스트 코인의 개수 $M$, 한 번의 이동에서 쓸 수 있는 비용 합의 최댓값 $L$이 공백 하나로 구분되어 주어진다. ($2 \le N \le 100$, $1 \le M \le 100$, $1 \le L \le 1000$)

둘째 줄에는 정류장의 위치를 나타내는 서로 다른 양의 정수 $N$개가 공백 하나로 구분되어 주어진다. 정렬되어 있지 않을 수 있고, 각 위치는 $1000$ 이하다.

이어지는 $M$개 줄에는 코인의 비용 $C$와 추진력 $V$가 공백 하나로 구분되어 주어진다. ($1 \le C, V \le 100$)

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 위치가 가장 작은 정류장에서 위치가 가장 큰 정류장으로 갈 수 없으면 -1을, 갈 수 있으면 최소 이동 횟수를 출력한다.

정류장의 위치가 3, 1, 6이고 $L = 4$이며 코인이 비용 3 추진력 2인 것과 비용 3 추진력 3인 것 두 개인 레벨을 보자. 위치 1에서 출발해 위치 6에서 끝내야 하므로 이동이 두 번 필요하다. 추진력 2인 코인으로 1에서 3으로 가고, 추진력 3인 코인으로 3에서 6으로 간다. 1에서 6으로 바로 가려면 두 코인을 함께 써야 하는데, 비용 합이 6이라 한계인 4를 넘는다.