Untitled

#include<bits/stdc++.h>
using namespace  std;
#define int long long
int sm(int i,int j,int *prf)
{
    if (i>j)return 0;
    if (i==0)return prf[j];
    return prf[j]-prf[i-1];
}
int n,k;
vector<vector<int>>dp(100,vector<int>(100,-1));
int rec(int i,int distinct,const vector<vector<int>>&cost,const vector<int>&v)
{
    if (i>=n)
    {
        return 1e18+5;
    }
    if (dp[i][distinct]!=-1)
        return dp[i][distinct];
    if (distinct==1)
    {
        return dp[i][distinct]=cost[i][n-1];
    }
    if (v[i]<=distinct)
    {
        return dp[i][distinct]=0;
    }
    int ans=1e18+5;
    for (int j=i;j<=n-1;j++)
    {
        ans=min(ans,cost[i][j]+rec(j+1,distinct-1,cost,v));
    }
    return dp[i][distinct]=ans;
}
void solve()
{
    cin>>n>>k;
    vector<int>a(n);
    for (auto &x:a)cin>>x;
    dp=vector<vector<int>>(n+5,vector<int>(n+5,-1));
    sort(a.begin(),a.end());
    int prf[n];
    prf[0]=1;
    for (int i=1;i<n;++i)
        prf[i]=prf[i-1]+a[i];
    vector<vector<int>>cost(n,vector<int>(n,1e18));
    for (int i=0;i<n;++i)
    {
        for(int j=i;j<n;j++)
        {
            if (j==i)
            {
                cost[i][i]=0;
            }
            else
            {
                for (int l=i;l<=j;l++)
                {
                    int nb=max(l-1-i+1,0ll);
                    int nb1=max(j-(l+1)+1,0ll);
                    int c1=nb*a[l]-sm(i,l-1,prf);
                    int c2=sm(l+1,j,prf)-nb1*a[l];
                    c2=max(c2,0ll);
                    c1=max(c1,0ll);
                    cost[i][j]=min(cost[i][j],c1+c2);
                }
            }
        }
    }
    vector<int>v(n);
    set<int>s;
    for (int i=n-1;i>=0;i--)
    {
        s.insert(a[i]);
        v[i]=s.size();
    }
    for (int distinct=1;distinct<=n;distinct++)
    {
        int r=rec(0,distinct,cost,v);
        if (r<=k)
        {
            cout<<distinct<<'\n';
            return;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
}