Problem Description

Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.
Alice will give Bob N sorted sequences, and the i-th sequence includes ai elements. Bob need to merge all of these sequences. He can write a program, which can merge no more than k sequences in one time. The cost of a merging operation is the sum of the length of these sequences. Unfortunately, Alice allows this program to use no more than T cost. So Bob wants to know the smallest k to make the program complete in time.

 

Input

The first line of input contains an integer t0, the number of test cases. t0 test cases follow.
For each test case, the first line consists two integers N (2≤N≤100000) and T (∑Ni=1ai<T<231).
In the next line there are N integers a1,a2,a3,...,aN(∀i,0≤ai≤1000).

 

Output

For each test cases, output the smallest k.

 

Sample Input

 

Sample Output

 

Source

 

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

const int N=1e5+,M=1e6+,inf=1e9+,mod=1e9+;

const ll INF=1e18+;

ll n,m;

ll a[N];

int check(int x)

{

    queue<ll>q;

    queue<ll>d;

    int yy=(n-)%(x-);

    if(yy!=)

    {

        for(int i=;i<x--yy;i++)

        q.push();

    }

    for(ll i=;i<=n;i++)

    q.push(a[i]);

    ll ans=;

    while(!q.empty()||!d.empty())

    {

        ll sum=;

        for(int i=;i<x;i++)

        {

            if(q.empty()&&d.empty())

                break;

            if(q.empty())

            {

                sum+=d.front();

                d.pop();

            }

            else if(d.empty())

            {

                sum+=q.front();

                q.pop();

            }

            else

            {

                int u=q.front();

                int v=d.front();

                if(u<v)

                {

                    sum+=u;

                    q.pop();

                }

                else

                {

                    sum+=v;

                    d.pop();

                }

            }

        }

        ans+=sum;

        if(q.empty()&&d.empty())

        break;

        d.push(sum);

    }

    if(ans>m)

        return ;

    return ;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld%lld",&n,&m);

        for(ll i=;i<=n;i++)

        scanf("%lld",&a[i]);

        sort(a+,a+n+);

        int st=,en=n;

        while(st<en)

        {

            int mid=(st+en)/;

            if(check(mid))

            en=mid;

            else

            st=mid+;

        }

        printf("%d\n",st);

    }

    return ;

}