무인 편의점과 위조 상품권

문제

Albert는 무인 편의점을 운영하고 있다. 고객들은 편의점에서 물건을 산 후 지폐 형태의 상품권을 이용하여 무인 기계를 통해 결제를 하는데, 상품권의 단위는 "비싼"것과 "싼" 것의 두 종류만 있다: $V_1$ 달러짜리 "싼" 상품권과 $V_2$ 달러짜리 "비싼" 상품권 ($0 \lt V_1 \lt V_2$ 는 정수). 편의상 기계는 거스름돈을 돌려주지 않는다.

매일 자정 Albert는 기계를 열어 상품권을 검사하는데, 간혹 위조된 상품권을 발견하기도 한다. 정확히 어떤 손님이 위조 상품권을 사용했는지 알아내고 싶지만, CCTV에 녹화된 내용을 세세히 체크해야하고, 이는 시간이 너무 오래 걸린다. "용의자"를 줄이기 위해 Albert가 활용할 수 있는 정보를 요약해보니 아래와 같았다:

현재 기계에는 싼 상품권 $C_1$장 그리고 비싼 상품권 $C_2$장이 들어있다.
총 $N$ 명의 손님이 결제를 했고, 결제 로그에 따르면 $i$ 번째 손님이 지불한 금액은 정확히 $A_i$ 달러 이다.
기계는 거스름돈을 주지 않으므로 $V_1 \times C_1 + V_2 \times C_2 = \sum_{i} A_i$ 임을 확인할 수 있다.
기계는 손님들이 지불한 상품권을 투입된 순서대로 보관한다 - 단, 싼 상품권과 비싼 상품권을 구분하여 각각 순서대로 보관한다.
기계에 $x$ 번째로 투입된 $V_2$ 달러 (비싼) 상품권이 위조 상품권이다 ($1 \le x \le C_2$).

Albert는 자신이 가진 정보를 최대한 활용하여 용의자의 수를 줄이고 싶다. $i$ 번째 고객이 용의자가 되려면 $i$ 번째 고객이 $x$번째 비싼 상품권을 지불함과 동시에 나머지 손님들도 정확히 자신의 결제금액 만큼만 지불할 수 있는 방법이 존재해야 한다. 구체적으로, $j$번째 손님이 사용한 싼 상품권이 $b_j$ 장이고 비싼 상품권이 $c_j$ 장 이라고 했을 때, 아래 조건을 모두 만족하는 $\{b_j, c_j\}$ 가 존재하면 $i$ 번째 고객은 용의자가 된다:

조건1: 모든 고객 $j$에 대하여 $0 \le b_j \le C_1$ 그리고 $0 \le c_j \le C_2$ 그리고 $V_1 b_j + V_2 c_j = A_j$
조건2: $\sum_{j=1}^{N} b_j = C_1$ 그리고 $\sum_{j=1}^{N} c_j = C_2$ (즉, 모든 고객의 $b_j, c_j$ 값을 더하면 $C_1, C_2$과 일치)
조건3: $\sum_{j=1}^{i-1} c_j \lt x \le \sum_{j=1}^{i} c_j$ (즉, $x$ 번째로 기계에 투입된 $V_2$ 달러 상품권은 $i$ 번째 고객이 투입함)

예를 들어 $V = [1, 5]$, $C = [10, 3]$, $N = 4$, $A = [5, 10, 5, 5]$ 그리고 $x = 1$ 이라 하자. 즉, 현재 기계에는 싼 상품권 $C_1=10$장, 비싼 상품권 $C_2=3$장이 있고 (따라서 총 금액은 $25$ 달러가 된다), 총 4명의 고객이 순서대로 $5$, $10$, $5$, $5$ 달러 만큼 결제하였음을 알 수 있다. $x = 1$ 이므로 비싼 상품권 중 가장 처음에 투입된 상품권이 위조 상품권임을 알 수 있다.

가령 $b = [0, 10, 0, 0], c = [1, 0, 1, 1]$ 라 하자.
- 1번 고객은 (위조된) 비싼 상품권 1장을 사용해 5달러를 결제했다.
- 2번 고객은 싼 상품권 10장을 사용해 10달러를 결제했다.
- 3번 고객과 4번고객은 각각 비싼 상품권 1장을 사용해 5달러를 결제했다.
- 상기한 3가지 조건을 $i=1$일 때 만족하므로 1번 고객은 용의자이다.
가령 $b = [5, 5, 0, 0], c = [0, 1, 1, 1]$ 라 하자.
- 1번 고객은 싼 상품권 5장을 사용해 5달러를 결제했다.
- 2번 고객은 싼 상품권 5장과 (위조된) 비싼 상품권 1장을 사용해 10달러를 결제했다.
- 3번 고객과 4번 고객은 각각 비싼 상품권 1장을 사용해 5달러를 결제했다.
- 상기한 3가지 조건을 $i=2$일 때 만족하므로 2번 고객은 용의자이다.
다른 다양한 $b, c$ 값들이 세 조건을 모두 만족하지만 $i = 3$ 혹은 $i = 4$일 때 세 조건을 만족하는 경우는 없으므로 고객 3, 4는 용의자가 아니다.

입력으로 $V, C, N, A, x$가 주어졌을 때, 용의자의 수를 추려 Albert를 도와주자. 위 예제의 경우 1, 2번 두 고객이 용의자이므로 정답은 2가 된다. 만약 세 조건을 만족하는 용의자가 0명이라면 -1을 출력한다 - 예제에서 보여지듯 Albert가 활용할 수 있는 정보에 오류가 있을 수도 있으므로, 용의자가 0명인 경우가 발생할 수 있다.

입력

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

각 테스트 케이스의 첫줄에는 $V_1, C_1, V_2, C_2$가 공백으로 구분되어 주어진다.

둘째 줄에는 $N$과 $x$가 공백으로 구분되어 주어진다.

셋째 줄에는 $N$개의 정수가 공백으로 구분되어 주어지는데, $A_i$ 값을 나타낸다.

출력

각 테스트 케이스의 정답인 용의자 수를 각 줄에 출력한다. 단, 용의자가 0명인 경우, -1을 출력한다.

제한

주어지는 모든 수는 정수이다.
$1 \le T \le 20$
$1 \le V_1 \lt V_2 \le 15$
$1 \le C_1, C_2 \le 10\,000$
$1 \le x \le C_2$
$1 \le N \le 100$
$1 \le i \le N$ 인 각 $i$ 에 대하여: $1 \le A_i \le 100$
모든 테스트 케이스에 대하여 $V_1 \times C_1 + V_2 \times C_2 = \sum_{i=1}^{N} A_i$ 임이 보장된다