C. Set or Decrease-Educational Codeforces Round 120 (Rated for Div. 2)

Problem - C - Codeforces

C. Set or Decrease

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer array a1,a2,…,ana1,a2,…,an and integer kk.

In one step you can

• either choose some index ii and decrease aiai by one (make ai=ai−1ai=ai−1);
• or choose two indices ii and jj and set aiai equal to ajaj (make ai=ajai=aj).

What is the minimum number of steps you need to make the sum of array ∑i=1nai≤k∑i=1nai≤k? (You are allowed to make values of array negative).

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The first line of each test case contains two integers nn and kk (1≤n≤2⋅1051≤n≤2⋅105; 1≤k≤10151≤k≤1015) — the size of array aa and upper bound on its sum.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the array itself.

It's guaranteed that the sum of nn over all test cases doesn't exceed 2⋅1052⋅105.

Output

For each test case, print one integer — the minimum number of steps to make ∑i=1nai≤k∑i=1nai≤k.

Example

input

Copy

4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10

output

Copy

10
0
2
7

Note

In the first test case, you should decrease a1a1 1010 times to get the sum lower or equal to k=10k=10.

In the second test case, the sum of array aa is already less or equal to 6969, so you don't need to change it.

In the third test case, you can, for example:

1. set a4=a3=1a4=a3=1;
2. decrease a4a4 by one, and get a4=0a4=0.

As a result, you'll get array [1,2,1,0,1,2,1][1,2,1,0,1,2,1] with sum less or equal to 88 in 1+1=21+1=2 steps.

In the fourth test case, you can, for example:

1. choose a7a7 and decrease in by one 33 times; you'll get a7=−2a7=−2;
2. choose 44 elements a6a6, a8a8, a9a9 and a10a10 and them equal to a7=−2a7=−2.

As a result, you'll get array [1,2,3,1,2,−2,−2,−2,−2,−2][1,2,3,1,2,−2,−2,−2,−2,−2] with sum less or equal to 11 in 3+4=73+4=7 steps.

It is obviously a greedy problem , We sort only the smallest ones -1 operation , The rest of the numbers are transformed to minimize the number of times .

There are two unknowns here , One is that the minimum value decreases x, One is a transformed number , What we know is that the numbers we transform must start from the back , We've chosen m The next one

So we have the relation

(m+1)(a1-x) + sum[n-m]-sum[1]  <= k

After the change , You can find , If we enumerate m, So for x In fact, there is a value range , Here we call ceil Function takes an upper bound to get a definite m Minimum x, Enumerate each m, Take the minimum value of sum .

# include<iostream>
# include<algorithm>
# include<math.h>
using namespace std;
typedef long long int ll;

double  a[200000+10],sum[200000+10];


int main()
{

    int t;

    cin>>t;

    while(t--)
    {
        ll n,k;

        cin>>n>>k;

        for(ll i=1;i<=n;i++)
        {
            cin>>a[i];
        }


        sort(a+1,a+1+n);

        for(int i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+a[i];

        }
        ll ans=0x7f7f7f7f7f7f7f7f;

        for(ll m=0;m<n;m++)
        {

            ll x=max((ll)0,(ll)ceil(a[1]-(k+sum[1]-sum[n-m])/(double)(m+1)));

            ans=min(ans,m+x);

        }

        cout<<ans<<endl;

    }


    return 0;

}