Recently, a shopping mall is making sale promotional activity. If you buy goods worth m yuan or more, they will return you r yuan cash. bailey is so poor that he wants to get r yuan with minimum cost. Please help him.


Input

The first line is an integer c which shows the number of cases. Each case contains 2 lines. The first line has 2 positive integers n and m, n is the number of goods. The second line contains n positive integers which are the price of each goods. You must remember that bailey hates to buy two same goods.(0<n<100, 0<m<1000)


Output

For each case print the minimum cost in a single line.


Sample Input


 2 2 100 50 70 3 100 50 50 70

Sample Output


 120 100

搞个input 和 output 范例 也不排列好

你是没有认真看题吧?

Sample Input
2
2 100
50 70
3 100
50 50 70

Sample Output
120
100

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

#define MSG
const int NUM = 80;

vector<unsigned int>  Goods;
bitset<NUM> bitSet;
unsigned int m, n, x;

void getInitMsg(void);
void recursion(unsigned int index, unsigned int uppound);
void deal();

int wmain(void)
{
    deal();
    return 0;
}

void getInitMsg(void)
{
#ifdef MSG
    cout << "输入商品数量: ";
#endif
    cin >> n;
#ifdef MSG
    cout << "输入优惠最低消费金额: " ;
#endif
    cin >> m;
#ifdef MSG
    cout << "输入商品的价格:";
#endif
    for (unsigned int sum=0,i=0; i<n; ++i)
    {
        cin >> x;
        sum += x;
        Goods.push_back(x);
        x = sum;
    }
}

void recursion(unsigned int index, unsigned int uppound)
{
    if (index >= uppound && uppound < n)
    {
        for (unsigned int sum=0, i=0; i<Goods.size(); ++i)
        {
            if (bitSet.test(i))
            {
                sum += Goods[i];
            }
        }
        if (sum >= m && sum <= x)
        {
            x = sum;
        }
        return;
    }
    else
    {
        bitSet.set(index);
        recursion(index+1, uppound);
        bitSet.reset(index);
        recursion(index+1, uppound);
    }
}

void deal()
{
    unsigned int i;

    getInitMsg();
    for (i=0; i<Goods.size(); ++i)
    {
        recursion(0, i);
    }

    if (x < m)
    {
        cout << "消费金额不足优惠条件" << endl;
    }
    else
    {
        cout << "最小的消费为: " << x << endl;
    }
}