Buying Sweets

Problem Statement:

Banknotes in the state of Strangeland don't have any regulated values like 1, 5, 10, 20, 50, 100, etc. In fact, it's possible to see any positive integer on a banknote of Strangeland. Indeed, this isn't the most convenient thing.

Ann is working as a sweet seller at a shop in Strangeland. Every kind of sweets in this shop has its own cost, and sweets of the same kind have the same cost.

Customers in Strangeland are strange. A customer points at some kind of sweets and gives several banknotes to the seller. This means that he wants to buy a positive number of sweets of that kind. He doesn't tell the exact number of sweets he wants to buy. The only thing Ann knows is: an 'adequate' customer won't give any extra banknotes. It means that if you throw away any banknote, the resulting amount of money won't be enough to buy the wanted number of sweets.

Ann has to determine the number of sweets the customer wants. Help Ann write a program which determines this number or tells that it's impossible.

Input

The first line of the input contains a single integer T, the number of test cases (no more than 20). T test cases follow. Each test case consists of two lines. The first of these lines contains two integers N and X (1 ≤ N, X ≤ 100) separated by a single space. N is the number of banknotes given by the customer. X is the cost of a single sweet of the chosen kind. The second of these lines contains N space-separated integers A_i (1 ≤ A_i ≤ 100), the values of the banknotes.

Output

For each test case output exactly one line containing a single integer:

• -1 if the customer is inadequate and has given extra banknotes, or
• K, the number of sweets the customer wants to buy. If there are several possible answers, output the largest of them.

Example

Input:
3
4 7
10 4 8 5
1 10
12
2 10
20 50

Output:
-1
1
7

Explanation

In the first test case, the total amount of money received from the customer is 27. He can't buy more than 3 sweets with this amount. If you throw away the banknote of value 5 (or of value 4), it will still be possible to buy 3 sweets. Hence the customer is inadequate.

In the second test case, it's clear that he wants to buy just one sweet (note that this number should be positive).

In the third test case, the total amount of money received is 70, which is enough for 7 sweets. The customer might want to buy only 6 sweets, but we are interested in the largest possible answer.

Problem Link : BUYING2 

The idea : 

The idea is very simple . If a user has to be inadequate then he must be exactly just above the requirement such that even if the smallest note is subtracted then he can not buy the same number of sweets . For this calculate two sums . Sum and smallsum. Now smallsum includes all the elements but the smallest one. Now check if sums when distributed yields same or different values. If they yield same values then they are certainly inadequate else they are adequate.

Take for example the first case

Sum= 27

and 

smallsum= 27-4=23

now (Sum/7)=3

and (smallsum/7)=3.

So both are equivalent. Hence answer will be -1.

The Code: 

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int length,costOfOne;
        scanf("%d %d",&length,&costOfOne);
        vector<int> v;
        int sum=0;
        int smallsum=0;
        for(int i=0;i<length;i++)
        {
            int k;
            cin>>k;
            v.push_back(k);
            sum+=v[i];
        }
       
        sort(v.begin(),v.end());
        smallsum=sum-v[0];
        int result1=(sum/costOfOne);
        int result2=(smallsum/costOfOne);
        if(result1==result2)
        {
            cout<<-1<<endl;
        }
        else
        {
            cout<<result1<<endl;
        }
    }
    return 0;

}