← 返回题目列表

Codeforces · 2139/B

B. 蛋糕系列

中文机器翻译题面 查看原题

枫想要为巧克力和香草烤一些蛋糕。

有一天,她发现了 $$$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 \le 10^5$$$) - 第 $$$i$$$ 个烤箱每秒烘烤的蛋糕数量。

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

输出

对于每个测试用例,输出一个整数,表示 Maple 在 $$$m$$$ 秒内可以收集的最大蛋糕数量。

示例

输入
复制

3
3 4
1 2 3
3 2
1 2 3
1 1000
100000

输出
复制

20
8
100000000

注意

对于第一个测试用例,一个最佳解决方案如下:

  1. 在第一秒结束时,烤箱分别包含 $$$1$$$、$$$2$$$ 和 $$$3$$$ 蛋糕。枫传送到烤箱 $$$3$$$ 并收集所有 $$$3$$$ 蛋糕。烤箱 $$$3$$$ 现在剩余 $$$0$$$ 蛋糕。
  2. 在第二秒结束时,烤箱分别包含 $$$2$$$、$$$4$$$ 和 $$$3$$$ 蛋糕。枫传送到烤箱 $$$1$$$ 并收集所有 $$$2$$$ 蛋糕。烤箱 $$$1$$$ 现在还剩下 $$$0$$$ 蛋糕。
  3. 在第三秒结束时,烤箱分别包含 $$$1$$$、$$$6$$$ 和 $$$6$$$ 蛋糕。枫传送到烤箱 $$$2$$$ 并收集所有 $$$6$$$ 蛋糕。烤箱 $$$2$$$ 现在剩余 $$$0$$$ 蛋糕。
  4. 在第四秒结束时,烤箱分别包含 $$$2$$$、$$$2$$$ 和 $$$9$$$ 蛋糕。枫传送到烤箱 $$$3$$$ 并收集所有 $$$9$$$ 蛋糕。烤箱 $$$3$$$ 现在剩余 $$$0$$$ 蛋糕。

枫总共收集了$$$3+2+6+9=20$$$蛋糕。

对于第二个测试用例,一个最佳解决方案如下:

  1. 在第一秒结束时,烤箱分别包含 $$$1$$$、$$$2$$$ 和 $$$3$$$ 蛋糕。枫传送到烤箱 $$$2$$$ 并收集所有 $$$2$$$ 蛋糕。烤箱 $$$2$$$ 现在剩余 $$$0$$$ 蛋糕。
  2. 在第二秒结束时,烤箱分别包含 $$$2$$$、$$$2$$$ 和 $$$6$$$ 蛋糕。枫传送到烤箱 $$$3$$$ 并收集所有 $$$6$$$ 蛋糕。烤箱 $$$3$$$ 现在剩余 $$$0$$$ 蛋糕。

枫总共收集了$$$2+6=8$$$蛋糕。