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.

显然是一件贪心题目，我们排序之后只对最小的进行-1操作，其余的数字跟着进行变换操作能使次数最少。

这里有两个未知量，一个是最小值减少的x,一个是变换的数字，已知的是我们变换的数字一定是从最后面开始的，我们设选了m个后面的

这样我们有关系式

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

变换之后，可以发现，如果我们枚举m，那么对于x其实是有一个取值范围，这里调用一下ceil函数取一下上界即可得到一个确定m的最小x,枚举每一个m,取和的最小值即可。

# 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;

}