挑战 NPH

【题目背景】

“所以，等我领图灵奖吧！”

【题目描述】

给定 $n$ 个物品，第 $i$ 个物品的价值为 $w_i$，每个物品可以购买任意多个。

给定 $k$，求按价值和从小到大排序后，第 $k$ 个的购买方案的价值和为多少。

两个购买方案不同，当且仅当对于某个物品，两者的购买数量不同。

【输入格式】

本题有多组测试数据。

第一行一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行两个整数 $n,k$。第二行 $n$ 个整数，表示 $w_i$。

【输出格式】

每组数据输出一个整数，表示价值和第 $k$ 大的购买方案的价值和。

【样例输入】

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

【样例输出】

100
1
3
4

【数据规模与约定】

对于 $100\%$ 的数据：$1 \le T \le 10, 1 \le n\le 10^3, 1 \le k \le 10^{12}, 1\le w_i,\sum{w_i} \le 10^3$。

·$Subtask1(10pts): n = 1$。

·$Subtask2(20pts): w_i =1$。

·$Subtask3(30pts): k\le 10^5$。

·$Subtask4(40pts): 无特殊限制$。

温馨提示：相信你代码的常数。

【来源】

在此键入。