记录编号	589199	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	挑战 NPH	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.644 s
提交时间	2024-07-03 17:28:35	内存使用	53.98 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define mp make_pair
#define in inline
#define re register
const int N = 1e3+10;
const ll mod = 1e9+7;


in ll read(){
   ll x = 0,f = 1;char c = getchar();
   for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
   for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
   return x * f;
}


int t,n,a[N];
ll k;


in bool check(int mid){
    ll ans = mid / a[2] + mid / a[1];
    for(int i = 1;i <= mid / a[1];i++)ans += (mid - a[1] * i) / a[2];
    return k <= ans;
}
in void solve2(){
    if(a[1] < a[2])swap(a[1],a[2]);
    int l = 1,r = (a[1] + a[2]) * sqrt(k) + 10;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    printf("%lld\n",l);
}


ll f[10000010];
in void solve3(){
    int m = 0,S = 0;
    for(int i = 1;i <= n;i++)S += a[i];
    m = S * ceil(pow(k,1.0/(double)n));
    for(re int i = 0;i <= m;i++)f[i] = 0;
    f[0] = 1;
    for(re int i = 1;i <= n;i++)
        for(re int j = 1;j <= m;j++)
            if(j >= a[i])f[j] += f[j-a[i]];
    for(re int i = 1;i <= m;i++){
        if(k <= f[i]){printf("%d\n",i);break;}
        else k -= f[i];
    }
}


in void solve(){
    n = read(),k = read();
    for(re int i = 1;i <= n;i++)a[i] = read();
    if(n == 1)printf("%lld\n",a[1] * k);
    else if(n == 2)solve2();
    else solve3();
}


int main(){
    freopen("NPH.in","r",stdin);
    freopen("NPH.out","w",stdout);
    t = read();
    while(t--)solve();
    
    
    return cerr<<clock()<<"ms"<<endl,0;
}