记录编号	601487	评测结果	AAWWWWWWWWWWWWWWWWWW
题目名称	3992.挑战 NPH	最终得分	10
用户昵称	LikableP	是否通过	未通过
代码语言	C++	运行时间	0.569 s
提交时间	2025-06-25 13:24:11	内存使用	2.94 MiB

#include <cstdio>
#include <cstring>
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
typedef long long ll;

namespace IO {
template <typename T>
T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-')
      f = -1;
  for (; isdigit(ch); ch = getchar())
    res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T>
void write(T x, char ed = '\n') {
  if (x < 0)
    x = -x, putchar('-');
  static int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}
} // namespace IO
using namespace IO;

const int MAXN = 1e3 + 10;
const int MAXM = 1e5 + 10;

int T;
int n;
ll k;
int w[MAXN];
ll cnt[MAXM];
ll pre[MAXM];

int main() {
  freopen("NPH.in", "r", stdin);
  freopen("NPH.out", "w", stdout);
  T = read<int>();
  while (T--) {
    memset(cnt, 0, sizeof cnt);
    memset(pre, 0, sizeof pre);
    n = read<int>(), k = read<ll>();
    for (int i = 1; i <= n; ++i) {
      w[i] = read<int>();
      cnt[w[i]]++;
    }

    if (n == 1) {
      write(1ll * w[1] * k);
      continue;
    }

    for (int price = 1;; ++price) {
      for (int first = 1; first <= price / 2; ++first) {
        int second = price - first;
        if (second == 0)
          continue;
        cnt[price] += cnt[first] * cnt[second];
      }
      pre[price] = pre[price - 1] + cnt[price];
      if (pre[price] >= k) {
        write(price);
        break;
      }
    }
  }
  return 0;
}

/*
 * 1 C(n, 1)
 * 2 C(n, 1) + C(n, 2)
 * 3 C(n, 1) + 2 * C(n, 2) + C(n, 3)
 * 4 C(n, 1) + 3 * C(n, 2) + 3 * C(n, 3) + C(n, 4)
 * 5 C(n, 1) + 4 * C(n, 2) + 6 * C(n, 3) + 4 * C(n, 4) + C(n, 5)
 *
 * 1*1 1*3
 * 1*2 1*2
 * 1*3 1*1
 * 1*1 1*1 1*2
 * 1*1 1*2 1*1
 * 1*2 1*1 1*1
 *
 * 1*1 1*4
 * 1*2 1*3
 * 1*3 1*2
 * 1*4 1*1
 *
 * 1*1 1*1 1*3
 * 1*1 1*3 1*1
 * 1*3 1*1 1*1
 * 1*1 1*2 1*2
 * 1*2 1*1 1*2
 * 1*2 1*2 1*1
 *
 *
 * 3 5
 * 1 2 3
 *
 * 1
 * 1*2 2
 * 1*3 1*1+2 3*1
 * 1*4 3+1 1+1+1+1 2+1+1 2+2 2+1+1
 * 1*5 1*1+2*2 1*3+2 1*2+3 2+3
 *
 * 3 5
 * 1 3
 *
 * 1: 1                1
 * 2: 1+1              1
 * 3: 1+1+1 3          1
 * 4: 1+1+1+1 1+3      2
 * 5: 1+4 2+3          2+1=3
 * 6: 1+5 2+4 3+3      3+2+1=6
 * 7: 1+6 2+5 3+4      6+3+2=11
 *
 *
 * 3 5
 * 1 2 3
 *
 * 1: 1                 1
 * 2: 1+1               1+1=2
 * 3: 1+2               2+1=3
 * 4: 1+3 2+2           3+2=5
 * 5: 1+4 2+3           5+6=11
 *
 * 3 5
 * 1 1 1
 * 1: 1                 3
 * 2: 1+1               9
 * 3: 1+2               27
 *
 *
 * 2 5
 * 3 5
 * 1:                   0
 * 2:                   0
 * 3:                   1
 * 4: 1+3 2+2           0
 * 5: 1+4 2+3           1
 * 6: 1+5 2+4 3+3       1
 * 7:
 *
 * 3+4
 * 1+2    1+1+2
 * 1+1+1  2+2
 */