CF2139B.Cake Collection

Maple 想为 Chocola 和 Vanilla 烤一些蛋糕。

有一天，她发现了 $n$ 个魔法蛋糕烤箱。第 $i$ 个烤箱每秒可以烤出 $a_i$ 个蛋糕。这些蛋糕会一直留在各自的烤箱中，直到被收集。

在每一秒结束时，她可以传送到任意一个烤箱（包括当前所在的烤箱），并收集该烤箱中至今为止累积的所有蛋糕。

你的任务是，求出 Maple 在 $m$ 秒内最多可以收集到多少蛋糕。

每个测试点包含多组测试数据。第一行为测试数据组数 $t$（$1 \le t \le 1000$）。以下是每组测试数据的描述。

每组测试数据的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^5$，$1 \leq m \leq 10^8$），分别表示魔法烤箱的数量和 Maple 收集蛋糕的秒数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^5$），表示第 $i$ 个烤箱每秒烤出的蛋糕数。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示 Maple 在 $m$ 秒内最多可以收集到的蛋糕数。

对于第一个测试用例，一种最优方案如下：

1. 第一秒结束时，各烤箱分别有 $1$、$2$、$3$ 个蛋糕。Maple 传送到烤箱 3，收集全部 $3$ 个蛋糕。此时烤箱 3 变为 $0$。
2. 第二秒结束时，各烤箱分别有 $2$、$4$、$3$ 个蛋糕。Maple 传送到烤箱 1，收集全部 $2$ 个蛋糕。此时烤箱 1 变为 $0$。
3. 第三秒结束时，各烤箱分别有 $1$、$6$、$6$ 个蛋糕。Maple 传送到烤箱 2，收集全部 $6$ 个蛋糕。此时烤箱 2 变为 $0$。
4. 第四秒结束时，各烤箱分别有 $2$、$2$、$9$ 个蛋糕。Maple 传送到烤箱 3，收集全部 $9$ 个蛋糕。此时烤箱 3 变为 $0$。

累计 Maple 共收集到 $3+2+6+9=20$ 个蛋糕。

对于第二个测试用例，一种最优方案如下：

1. 第一秒结束时，各烤箱分别有 $1$、$2$、$3$ 个蛋糕。Maple 传送到烤箱 2，收集全部 $2$ 个蛋糕。此时烤箱 2 变为 $0$。
2. 第二秒结束时，各烤箱分别有 $2$、$2$、$6$ 个蛋糕。Maple 传送到烤箱 3，收集全部 $6$ 个蛋糕。此时烤箱 3 变为 $0$。

最终 Maple 共收集到 $2+6=8$ 个蛋糕。

由 ChatGPT 5 翻译